백준 1557: 도로의 개수(Java)

✅ 문제 요약

• N×M 격자 도시에 도로가 건설됨.
• 도로는 격자의 가로선 또는 세로선에 해당.
• 일부 도로는 공사 중이므로 통행 불가.
• (0,0)에서 (N,M)까지 이동하는 경로의 수를 구하라.
• 오른쪽 또는 아래쪽 방향으로만 이동 가능.

---

🔍 알고리즘 설계

• DP[i][j] = (0,0)부터 (i,j)까지 가는 경로 수
• 인접한 두 좌표 사이의 도로가 막혀있다면 그 방향으로 이동 불가.
• 공사 중 도로는 (i1, j1, i2, j2)로 주어짐 → Set으로 관리.

import java.util.*;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        int K = sc.nextInt();
        dp = new long[N + 1][M + 1];

        for (int k = 0; k < K; k++) {
            int i1 = sc.nextInt();
            int j1 = sc.nextInt();
            int i2 = sc.nextInt();
            int j2 = sc.nextInt();
            block.add(i1 + " " + j1 + " " + i2 + " " + j2);
            block.add(i2 + " " + j2 + " " + i1 + " " + j1);
        }

        dp[0][0] = 1;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                if (i > 0 && !block.contains((i - 1) + " " + j + " " + i + " " + j)) {
                    dp[i][j] += dp[i - 1][j];
                }
                if (j > 0 && !block.contains(i + " " + (j - 1) + " " + i + " " + j)) {
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
        System.out.println(dp[N][M]);
    }
}

---

📌 핵심 포인트

• DP를 활용하여 각 좌표까지의 경로 수를 누적
• 공사 중 도로는 Set<String>으로 관리하여 양방향 차단
• 좌표 인덱스를 (i, j) 형식으로 명확하게 관리

---

⏱ 시간 복잡도 분석

• 시간 복잡도: O(N × M)
• 공간 복잡도: O(N × M)
• N, M ≤ 100 이므로 충분히 처리 가능