[Boj_1577] 도로의 개수

📎 문제 링크

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보다 작거나 같은 자연수이다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 5
• 🔔  문제 유형 : 다이나믹 프로그래밍
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

다이나믹 프로그래밍을 이용해 해결할 수 있는 문제이다.

 

세준이는 항상 최단 거리로만 이동하므로, 이동할 수 있는 방향은 오른쪽 또는 아래쪽 두 가지뿐이다.

따라서, (0, 0)에서 (N, M)까지 도달하는 경로의 경우의 수를 dp 배열을 이용해 계산할 수 있다.

 

1️⃣ 이동 가능 여부를 저장하는 map 배열

각 위치 (i, j)에서 이동할 수 있는 방향을 저장하기 위해 3차원 배열을 선언한다.

• map[i][j][0] → 아래쪽 이동 가능 여부
• map[i][j][1] → 오른쪽 이동 가능 여부
• 값이 -1이면 해당 방향으로 이동 불가능

공사 중인 도로가 있을 경우, 이동이 불가능하도록 설정한다.

이때, 공사 중인 도로의 정보 (x1, y1) → (x2, y2)의 입력 순서가 뒤바뀌었을 수도 있다.

따라서, 올바르게 처리할 수 있도록 두 좌표를 정렬하는 과정이 필요하다.

 

2️⃣ DP 배열 정의 및 점화식

dp[i][j] → (0,0)에서 (i, j)까지 갈 수 있는 경로의 개수이다.

먼저, dp[0][0] = 1로 초기화한다. (출발점)

 

• 오른쪽 이동 가능 (map[i][j][1] != -1) → dp[i][j] += dp[i][j-1] (j-1 ≥ 0)
• 아래쪽 이동 가능 (map[i][j][0] != -1) → dp[i][j] += dp[i-1][j] (i-1 ≥ 0)

 dp의 값이 int의 범위를 벗어나므로 타입을 long으로 지정해야 한다.

 

 

3️⃣ 최종 결과

dp[n][m] 값이 (0, 0) → (N, M)까지의 모든 최단 경로 수가 된다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 11980KB
시간 : 68ms

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 도로의 가로
        int m = Integer.parseInt(st.nextToken()); // 세로

        // map[i][j][k] : (i, j)에서 k 방향으로 갈 수 있는지
        // 왼쪽에서 오른쪽으로 / 위에서 아래로 -> 이 두 방향으로만 이동 가능하다.
        int[][][] map = new int[101][101][2];
        long[][] dp = new long[101][101]; // *

        int k = Integer.parseInt(br.readLine()); // 공사중인 도로의 개수

        // 공사중인 도로 정보
        int x1, y1, x2, y2;
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            // -1이라면 이동 불가능
            if (y1 == y2) {
                // 입력의 순서가 바뀔 수도 있으므로
                // 값을 바꿔주는 과정 필요
                if (x1 > x2) {
                    int tmp = x1;
                    x1 = x2;
                    x2 = tmp;
                }
                map[x2][y1][0] = -1; // 아래로 이동 불가능 / 왼쪽에서 오른쪽 이동
            }

            if (x1 == x2) {
                if (y1 > y2) {
                    int tmp = y1;
                    y1 = y2;
                    y2 = tmp;
                }
                map[x1][y2][1] = -1; // 왼쪽 이동 불가능 / 위에서 아래로 이동
            }
        }

        dp[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (map[i][j][0] != -1 && i-1 >= 0) { // x 방향 이동 가능
                    dp[i][j] += dp[i-1][j];
                }
                if (map[i][j][1] != -1 && j-1 >= 0) { // y 방향 이동 가능
                    dp[i][j] += dp[i][j-1];
                }
            }
        }

        System.out.println(dp[n][m]);
        br.close();
    }
}

 

구현하는 데 조금 오래 걸리긴 했지만, dp를 풀면서 재밌다는 생각이 들었던 문제이다.

다른 dp 문제도 풀어봐야지 ! 🔥