[백준] JAVA - 1577. 도로의개수

https://www.acmicpc.net/problem/1577

1577번: 도로의 개수

생각

스터디원의 도움을 받아 풀었습니다!!! (따봉우재야 고마워~)

 

0. dp의 값이 int의 범위를 벗어나므로 타입을 long으로 해줘야합니다!!! (int로 하면 틀렸다고 나옵니다ㅠㅠ 범위 체크를 꼭 해주자.. 메모메모)

1. 우선 맵을 반대로 뒤집어서 좌표의 출발점을 (0,0) 도착점을 (N,M)으로 잡아줍니다.

2. 이때 이동할수있는 방향은 두가지로 왼쪽->오른쪽, 위->아래인 경우밖에 없습니다. 따라서 이동방향에 따른 상태를 나타내기 위해 3차원 배열을 선언합니다. map[k][i][j] : k방향으로 (i,j) 위치로 이동할수있는지 판단. -1이라면 이동 불가능

3. map[0][i][j] != -1 일때 x방향으로 이동이 가능하므로 i-1 이 0이상인지 체크하고 dp[i][j] += dp[i-1][j]

4. map[1][i][j] != -1 일때 y방향으로 이동이 가능하므로 j-1 이 0이상인지 체크하고 dp[i][j] += dp[i][j-1]

5. dp[n][m] 출력

 

github.com/SSAFY5thGwangJu4C/Algorithm_AlgoGaZa/blob/main/kwj1270/4%EC%9B%94%202%EC%A3%BC/1577_%EB%8F%84%EB%A1%9C%EC%9D%98%EA%B0%9C%EC%88%98_1%EB%B2%88.java

SSAFY5thGwangJu4C/Algorithm_AlgoGaZa

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1577_도로의개수 {
	static int R,C;
	static int K; // 공사중인 도로의 개수
	static int map[][][]; //map[i][j][k] : (i,j)에서 k방향으로 갈수있는지 판단
	static long[][] dp;
	static int ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		C = Integer.parseInt(st.nextToken()); // 가로
		R = Integer.parseInt(st.nextToken()); // 세로

		K = Integer.parseInt(br.readLine());
		
		map = new int[2][101][101];
		dp = new long[101][101];
		
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			if(y1 == y2) {
				if(x1 > x2) {
					int temp = x1;
					x1 = x2;
					x2 = temp;
				}
				map[0][x2][y1] = -1; //x2 -> x1 이 막혀있을때 : 왼쪽에서 오른쪽 이동 불가능
			}
			
			if(x1 == x2) {
				if(y1 > y2) {
					int temp = y1;
					y1 = y2;
					y2 = temp;
				}
				map[1][x1][y2] = -1; //y2 -> y1 이 막혀있을때 : 위에서 아래로 이동 불가능
			}
			
		}
		dp[0][0] = 1;
		
		for (int i = 0; i <= C; i++) {
			for (int j = 0; j <= R; j++) {
				if(map[0][i][j] != -1 && i-1 >= 0) {
					dp[i][j] += dp[i-1][j];
				}
				if(map[1][i][j] != -1 && j-1 >= 0) {
					dp[i][j] += dp[i][j-1];
				}
				
			}
		}
		
		System.out.println(dp[C][R]);
		
	}


}