[백준] 도로의 개수 - Java

문제 출처

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

문제

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

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

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

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

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

입력

첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자연수이다. 셋째 줄부터 K개 줄에는 공사중인 도로의 정보가 a b c d와 같이 주어진다. a와 c는 0보다 크거나 같고, N보다 작거나 같은 자연수이고, b와 d는 0보다 크거나 같고, M보다 작거나 같은 자연수이다. 그리고, (a, b)와 (c, d)의 거리는 항상 1이다.

출력

첫째 줄에 (0, 0)에서 (N, M)까지 가는 경우의 수를 출력한다. 이 값은 0보다 크거나 같고, 263-1보다 작거나 같은 자연수이다.

예제 입력 1

6 6
2
0 0 0 1
6 6 5 6

예제 출력 1

252

예제 입력 2

1 1
0

예제 출력 2

2

예제 입력 3

35 31
0

예제 출력 3

6406484391866534976

예제 입력 4

2 2
3
0 0 1 0
1 2 2 2
1 1 2 1

예제 출력 4

0

풀이 방법

• dfs로 방법 찾으면 무조건 시간초과가 날게 뻔하기(예제3번보면 알듯)에.. dp를 이용했다.

1. Set을 하나 만들어서, 공사 정보를 추가한다.
-> 이 때 배열로 만들어서 할거면, 공사 정보는 N, M 으로 제공되기 때문에 뒤집어서 넣어야한다. 이것 때문에 30%에서 계속 틀려서 반례 찾아봤다...
2. 이후 완전 탐색을 수행하며 dp에 값을 저장한다.

경로의 수는 어떻게 찾나?

• 예시로 4x4 에서, (0, 0) <-> (1, 0) 부분과 (2, 3) <-> (2, 4)부분이 공사 현장이라고 해보자.

• 최적화된 도로를 찾는다고 했으므로 세준이는 오른쪽 또는 아래 방향의 경로만 선택할 수 있다.
• 여기서 해당 좌표까지 갈 수 있는 경우의 수는 다음과 같다.

• 그림을 보면 알겠지만, 좌표 (R, C) 까지 갈 수 있는 경우의 수는
  • 왼쪽에서 들어오는 경우
  • 위쪽에서 들어오는 경우
• 이 두가지 뿐이므로, (R, C)까지 가는 경우의 수 = (R - 1, C)까지 가는 경우의 수 + (R, C - 1) 까지 가는 경우의 수 가 성립한다.

풀이 코드

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

public class Main {
    static int N, M, K;
    static long[][] dp;
    static Set<String> construction = new HashSet<>();

    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());
        M = Integer.parseInt(st.nextToken());
        dp = new long[M + 1][N + 1];
        K = Integer.parseInt(br.readLine());

        // 공사 정보
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int y1 = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            //공사 패치할 때, 작은 수를 앞으로 정렬한다.
            if(x1 > x2 || y1 > y2){
                construction.add(x2 + ", " + y2 + " - " + x1 + ", " + y1);
            }
            else {
                construction.add(x1 + ", " + y1 + " - " + x2 + ", " + y2);
            }   
        }

        dp[0][0] = 1;

        for(int i = 0; i <= M; i++){
            for(int j = 0; j <= N; j++){
                if(i == 0 && j == 0){
                    continue;
                }

                //위에서 올 수 있는 경우
                if(i > 0 && !construction.contains((i - 1) + ", " + j + " - " + i + ", " + j)){
                    dp[i][j] += dp[i - 1][j];
                }
                
                //왼쪽에서 올 수 있는 경우
                if(j > 0 &&!construction.contains(i + ", " + (j - 1) + " - " + i + ", " + j)){
                    dp[i][j] += dp[i][j - 1];
                }

                // System.out.println(i +", " + j +"의 현재 값 : " + dp[i][j]);
            }
        }

        System.out.println(dp[M][N]);

    }
}

결과

회고

• 좌표 때문에 더 헷갈려서.. 문제 자체는 어렵진 않다.