(Java/자바) - 백준(BOJ) 1577번 : 도로의 개수

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

1577번: 도로의 개수

---

• 문제 : 

세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.

 

따라서, 아래 그림과 같이 생겼다.

 

세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.

 

세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.

 

(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

DP 문제였습니다.

 

풀이입니다.

 

 

우선, 일반적으로 2차원 행렬에서 (0,0) -> (x,y) 까지 경로의 개수를 찾기 위해 사용하는 방법은

dp[i][j] = dp[i-1][j] + dp[i][j-1] 입니다.

 

이 문제에서는 위의 로직을 기본으로 하여 현재 탐색중인 좌표의 위나 왼쪽에 공사중인 도로가 있는 경우에는 해당 경로의 개수를 더해주지 않으면 됩니다.

 

1. Hashset을 이용하여 이전좌표 -> 현재좌표로 이동하는 공사중인 도로좌표의 쌍이 존재하는지 중복 여부를 체크해도 되고.

2. 단순히 배열에 넣어 O(K)의 시간복잡도로 탐색해도 됩니다. (이 경우는 비효율적임)

3. 저는 road라는 3차원 boolean 배열을 사용하여 어떤 좌표에서 아래 또는 오른쪽으로 뻗어나가는 공사중인 도로가 있을 경우 boolean 값을 true로 설정해주었습니다.

 

현재 탐색중인 좌표에서 왼쪽, 위쪽 좌표의 boolean값이 false일 경우에만 경로의 개수를 더해주었습니다.

 

 

 

 

 

---

• 소스코드 : 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N,M,K,a,b,c,d;
	static long[][] dp;
	static boolean[][][] road;
	static boolean col, row;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // col
		M = Integer.parseInt(st.nextToken()); // row
		K = Integer.parseInt(br.readLine());
		road = new boolean[M+1][N+1][2];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken()); // y
			b = Integer.parseInt(st.nextToken()); // x
			c = Integer.parseInt(st.nextToken()); // y
			d = Integer.parseInt(st.nextToken()); // x
			if (a < c || b < d) { // 더 작은 쪽에서 (왼쪽이나 위쪽에 있는 좌표에서) 연결해주기 위함
				if (a < c) { // 왼쪽에 있는 좌표 기준으로 아래로 연결된 도로가 공사중임
					road[b][a][0] = true;
				}
				else { // 위에 있는 좌표 기준으로 아래로 연결된 도로가 공사중임
					road[b][a][1] = true;
				}
			} else {
				if (c < a) { // 왼쪽에 있는 좌표 기준으로 아래로 연결된 도로가 공사중임
					road[d][c][0] = true;
				}
				else { // 위에 있는 좌표 기준으로 아래로 연결된 도로가 공사중임
					road[d][c][1] = true;
				}
			}
		}
		dp = new long[M+1][N+1];
		for (int i = 1; i <= N; i++) { // 첫 경로 표시, 갈 수 없을 때까지 1개의 경로를 가짐
			if (road[0][i-1][0]) break;
			dp[0][i] = 1;
		}
		for (int i = 1; i <= M; i++) { // 첫 경로 표시, 갈 수 없을 때까지 1개의 경로를 가짐
			if(road[i-1][0][1]) break;
			dp[i][0] = 1;
		}
        for (int i = 1; i <= M; i++) {
			for (int j = 1; j <= N; j++) {
				if(!road[i][j-1][0]) dp[i][j] += dp[i][j-1]; // 왼쪽 도로가 공사중이 아닐 경우
				if(!road[i-1][j][1]) dp[i][j] += dp[i-1][j]; // 위쪽 도로가 공사중이 아닐 경우
			}
		}
		System.out.println(dp[M][N]);
	}
}