[백준 1157] 도로의 개수 - JAVA

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

 

 

시행 착오:

 

1. N이 가로를 의미한다. 배열은 정사각형이 아니므로 N이 세로를 의미하면 답이 달라진다. (도로 정보까지 맞춰서 반대로 저장하면 상관없음)

 

2. 도로를 기록할 때 양방향으로 저장했다가 틀렸다.

if (a == c) {
load[b][a][0] = d;
load[d][a][0] = b;
} 
else {
load[b][a][1] = c;
load[b][c][1] = a;
}

 

이러면 한 지점에 연결된 도로의 정보가 2개 이상이면 모두 기록하지 못하고, 덮어 씌워진다.

 

 

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

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());
    int K = Integer.parseInt(br.readLine());

    long[][] dp = new long[M + 1][N + 1];
    int[][][] load = new int[M + 1][N + 1][2];

    for (int i = 0; i <= M; i++) {
      for (int j = 0; j <= N; j++) {
        load[i][j][0] = -1;
        load[i][j][1] = -1;
      }
    }

    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 (a == c) { // 세로 도로 공사
        load[Math.min(b, d)][a][0] = Math.max(b, d);
      } else { // 가로 도로 공사
        load[b][Math.min(a, c)][1] = Math.max(a, c);
      }
    }

    dp[0][0] = 1;
    for (int i = 0; i <= M; i++) {
      for (int j = 0; j <= N; j++) {
        if (i > 0 && load[i - 1][j][0] != i) {
          dp[i][j] += dp[i - 1][j];
        }

        if (j > 0 && load[i][j - 1][1] != j) {
          dp[i][j] += dp[i][j - 1];
        }
      }
    }

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