문제 탐색하기

입력 자료 정리

1. N은 도로의 가로크기, M은 도로의 세로크기다
2. k는 앞으로 주어질 공사된 지점의 도로 개수다
3. 이후 들어오는 값은 a,b / c,d로 지점이 나뉘며 a,c는 가로 좌표이고 b,d는 세로 좌표다

해결방법 추론

1. 좌표평면이니 BFS/DFS중 하나를 사용해서 해결할 수 있겠다고 생각했다
2. 문제에서 구하는 것은 최단거리로 갈 때, 목적지까지 가는 서로 다른 경로의 경우의 수이다
3. bfs로는 구할 수 없고, dfs로 해당 방법을 구할 수 있겠다고 생각하였다
4. 하지만 입력값을 보니 dfs로는 해결할 수 없겠다고 생각하였다
5. n과 m의 최대 입력값은 100이고, 최단거리로 가는 경우는 그림을 뒤집어서 생각했을 때,
   아래방향과 오른쪽 방향으로 가는 2가지 경우이다
6. 따라서 나올 수 있는 최대의 경우의 수는 2^10,000이다.
7. 시간제한에 걸려서 해당 방법으로는 도저히 해결할 수가 없다.
8. 그렇다면 어떻게 문제를 풀 수 있을까?
9. 특정 좌표 지점으로 오는 경우를 누적하여 합산한다면 목적지까지 오는데
   필요한 경로의 경우의 수를 구할 수 있을 것이다!
10. 즉 DP로 해당 문제를 해결할 수 있다!

좌표평면에서의 DP

1. 최단거리로 목적지까지 간다고 문제에 나와있다.
   따라서 불필요하게 왔던 길을 가지는 않고, 오로지 최선의 선택만 해서 이동한다
2. 만약 최단거리로 가지 않는다면, (1,1)까지 오는 경우는 상하좌우에서 오는 4가지 경우일 것이다
3. 하지만 0,0에서 목적지까지 최단 경로로 간다면 (1,1)에 오는 경우는 (1,0), (0,1) 2가지 경우일 것이다
4. 즉 그림을 뒤집었을 때, 그 지점의 왼쪽과 위쪽에서 오는 2가지 경우만 체크해주면 된다!

좌표평면 양끝 모서리

1. 한가지 주의할 점은 최단거리로 목적지까지 갈때,
   양끝 모서리는 자신의 이전 세로, 가로 모서리 좌표로 오는 경우만 존재한다
2. 즉 (2,0)일때, (1,0)으로만 오는 경우가 존재하고, (0,2)일때, (0,1)로 오는 경우만 존재한다
3. 따라서 좌표평면의 양 끝 모서리 좌표에 대해서는 모두 1로 초기화하면 된다.
4. 물론 최초 지점인 0,0도 시작하는 경우인 한가지 경우만 존재한다!

시간복잡도 계산

1. 이제 점화식을 세우기 위한 모든 준비는 끝났다.
2. 하지만 이전에 DP도 과연 시간제한안에 들어올 수 있는지 시간복잡도를 계산해보자
3. k는 n과 m보다 작으므로 시간복잡도 계산에서 제외된다
4. n과 m와 관련된 로직들을 보았을 때, 좌표 평면 양끝 모서리 초기화하는 연산은 각각 n과 m이다
5. 이어서 dp 점화식을 실행했을 때를 생각하면 이전 가로, 이전 세로 길 두가지 길에 대해서
   모두 고려해서 넣어줘야하므로 n x m만큼의 연산이 발생할 것이다
6. 따라서 시간복잡도는 O(n x m)이 된다!
7. 둘다 최대가 100이므로 시간제한안에 문제를 해결할 수 있다!

점화식 추론

1. 점화식 자체는 쉽게 세울 수 있다
2. 모서리 지점을 제외하고는 다음과 같은 점화식이 나오게 된다
   dp[i] = dp[i-1][j] + dp[i][j-1]
3. 현재 지점의 왼쪽에서 오는 경우의 누적된 합산과 위쪽에서 오는 경우의 누적된 합산을 더하면
   현재 지점까지 오는 모든 경우의 수가 된다

공사 지점에 대한 이해

1. 예외사항(모서리, 최초 지점)과 점화식에 대한 설계는 모두 끝났다.
2. 하지만 이 문제에서 한가지를 더 고려해야한다. 바로 공사지점에 대한 처리다
3. 공사지점은 특점 점이 아닌 두 지점 사이의 선을 의미한다
4. 공사 지점에 해당하는 선을 파악해서 미리 체크해주어야 하는데...
   어떻게 표현할 수 있을지 고민이 필요하다

공사 지점 관리 설계

1. 일단 두 지점 사이의 거리는 항상 1이라고 나와있다.
   따라서 두 지점은 가로 한칸이나 세로 한칸 떨어져 있는 것이고,
   다시 말하면 가로가 같거나 세로가 같거나 둘중 하나라는 의미이다
2. 그리고 이 문제에서는 최단거리로만 이동한다고 하였다.
3. 두 조건을 보았을 때, 두 지점은 시작지점과 도착지점 두가지로만 한정된다는 것이고
   시작지점만 막는다면 그 길은 공사지점으로 선택되지 않음을 알 수 있다.
4. 따라서 시작지점의 위치에 체크를 해서 그 지점에 해당하지 않는 경우만 dp로 초기화한다면
   문제의 조건을 만족하면서 모든 경로를 탐색할 수 있을 것이다

코드 설계하기

입력값 상태 관리하기

1. 크기에 해당하는 n,m,k와 공사지점에 해당하는 a,b,c,d는 모두 변수로 관리한다
2. dp는 long타입의 2차원 배열로 선언해준다.

공사 지점 상태 관리하기

1. 공사지점은 선이며, 가로선과 세로선 두가지 경우로만 나누어진다
2. 모든 가로선과 세로선은 배열의 크기인 n+1, m+1 크기만큼 존재할 것이다.
3. 해당 지점의 선을 체크하면 공사지점이 되는 것이고 아니면 갈 수 있는 지점으로 판단할 것이다
4. 따라서 boolean 2차원 배열 타입으로 선언한다
5. k만큼 입력을 받으며, a,b,c,d 지점을 변수로 받아준다
6. a,c는 y좌표 b,d는 x좌표이다
7. y좌표가 같은 경우와 그렇지 않은 경우로 나누어서 확인한다
8. 이때, y좌표가 같은 경우가 아니면 그냥 x좌표가 같은경우로 봐도 되는데,
   두 지점 사이의 거리가 1이고 최단거리로만 이동한다고 했기 때문이다
9. y좌표가 같을 때는 x좌표가 더 작은 쪽을 체크, x좌표가 같을 때는 y좌표가 더 작은 쪽을 체크한다
10. 이때 y좌표나 x좌표는 어차피 같기 때문에 둘중 아무좌표나 사용해도 상관없다

DP 최초값과 양끝 모서리 초기화

1. DP의 최초값인 0,0은 1로 초기화한다
2. 양끝 모서리는 공사지점에 각각 1로 초기화한다
3. 이때 이전 지점의 가로선이나 세로선이 공사지점이라고 한다면,
   이후 길에 대해서는 모두 갈 수 없으므로 break로 탈출한다

DP식 구현하기

1. 공사지점 때문에 위에서 구한 DP 점화식을 조금 변형하여야 한다
2. 이전 지점에서의 가로선과 세로선이 공사지점이 아니라면
   각각의 점화식을 부분을 더하는 식으로 한다
3. dp[i][j] += dp[i-1][j]; / dp[i][j] += dp[i][j-1] 이런식으로 더해준다

출력 설계하기

1. 목적지의 dp인 n,m의 dp 값을 출력하면 정답이 된다

주의할점

1. 이 문제는 한번에 시도하기는 했는데, 예제 입력 몇가지가 자꾸 다르게 나와
   시행착오를 겪었던 문제다
2. 원인은 이 문제에서 n과 m을 가로/세로로 주었기 때문이었다.
3. 보통 n은 세로, m은 가로로 생각하기 때문에 공사지점도 반대로 생각하였고,
   그렇기에 일부 예제는 맞는데 다른 예제를 틀리는 시행착오를 겪었다
4. 다행히 문제를 다시 읽어 원인을 발견할 수 있었고, 1회차 시도로 해당 문제를 해결하게 되었다

정답코드

(1회차 시도 성공!)

import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[][] dp = new long[n+1][m+1];

        boolean[][] horizon = new boolean[n+1][m+1];
        boolean[][] vertical = new boolean[n+1][m+1];



        int k = Integer.parseInt(br.readLine());
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            if(b == d){
                if(a > c){
                    horizon[c][b] = true;
                }else{
                    horizon[a][b] = true;
                }
            }else{
                if(b > d){
                    vertical[a][d] = true;
                }else{
                    vertical[a][b] = true;
                }
            }
        }
        dp[0][0] = 1;

        for (int i = 1; i < n+1; i++) {
            if(horizon[i-1][0]){
               break;
            }
            dp[i][0] = 1;
        }

        for (int i = 1; i < m+1; i++) {
            if(vertical[0][i-1]){
                break;
            }
            dp[0][i] = 1;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if(!horizon[i-1][j]){
                    dp[i][j] += dp[i-1][j];
                }

                if(!vertical[i][j-1]){
                    dp[i][j] += dp[i][j-1];
                }
            }
        }


        bw.write(dp[n][m] + "");

        br.close();
        bw.close();
    }

}

문제 링크

1577번 - 도로의 개수