[백준] 1577: 도로의 개수 - JAVA

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

 

풀이

n x m 사이즈의 도시에서 (0, 0) 부터 (n, m)까지 가는 경우의 수를 구해야 한다.

 

다만, 공사중인 도로가 있어서 지나갈 수 없는 곳이 있다.

 

`0 0 0 1` 과 같이 주어지는데 이는 (0, 0)에서 (0, 1)로 가는 도로를 이용할 수 없다는 것을 말한다.

 

3차원배열을 만들어서 가로 도로, 세로 도로의 공사 여부를 저장했다.

 

그 후, (0, 0)으로 부터 가로로만 갔을 때, 세로로만 갔을 때를 1로 채워주고 bottom-up방식으로 dp배열을 채워주었다.

 

---

 

메모리: 14312KB
시간: 128ms
언어: Java 11

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));
        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];
        int[][][] block = new int[n + 1][m + 1][2];

        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) {
                block[Math.min(a, c)][b][0] = 1;
            } else {
                block[a][Math.min(b, d)][1] = 1;
            }
        }

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

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

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

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

}