[백준/G5/DP/자바] 1577 도로의 개수

💡 문제

 

세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다.

도시의 가로 크기는 N이고, 세로 크기는 M이다.

또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.

따라서, 아래 그림과 같이 생겼다.

 

세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.

세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다.

하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다.

도로가 공사 중일 때는, 이 도로를 지날 수 없다.

(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.

 

⌨ 입력

 

첫째줄 0 <= N, M <= 100

둘째줄 도로의 개수 K ( 0 <= K <= 50 )

셋째줄 공사중인 도로 a b c d ( 항상 거리 1 )

 

💻 출력 / 제한

 

( 0, 0 ) -> ( N, M ) 까지 가는 경우의 수 출력  (  2의 63승 - 1 까지 범위 )

 

---

 

풀이 방법

 

문제 유형 : DP ( 다이나믹 프로그래밍 )

 

DP 풀이는 간단하다.

그림을 뒤집어서 그릴때,  최단 거리로 가려면 오른쪽 / 아래 만 갈 수 있다.

 

문제는 공사중인 도로를 표기하는 방법에 주의 해야 한다.

 

1개 배열 공사중 표시를  할 경우

int[][] ban = new int[N + 1][M + 1];
       
for(int i = 0; i < forbidCount; i++){
    int[] rowAndCol = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    ban[rowAndCol[0]][rowAndCol[1]] = 1; ban[rowAndCol[2]][rowAndCol[3]] = 1;
  }

 

 

 

파란색으로 표시된 부분을 보시면 됩니다.

 

하나의 배열에 체크를 하면 (2,0) / (2,1) 둘다 체크 되어 있는데 실제로는 공사중이 아닙니다.

 

따라서 두개의 배열에 나눠서 체크 해야 합니다.

 

2개 배열 공사중 표시를  할 경우

 long[][] prohibitRow = new long[N + 1][M + 1];
 long[][] prohibitCol = new long[N + 1][M + 1];
 
for(int i = 0; i < forbidCount; i++){
            int[] rowAndCol = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            if(rowAndCol[1] == rowAndCol[3]) {
                prohibitRow[Math.min(rowAndCol[0],rowAndCol[2])][rowAndCol[1]] = 1;
            }
            else{
                prohibitCol[rowAndCol[0]][Math.min(rowAndCol[1],rowAndCol[3])] = 1;
            }
        }

 

 

배열을 두개 사용 한다면 공사중인 곳을 정확 하게 표기 할수 있습니다.

 

---

 

전체 코드

import java.io.*;
import java.util.stream.Stream;

public class WayCount1577 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] NM = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = NM[0]; int M = NM[1];
        int forbidCount = Integer.parseInt(br.readLine());

        long[][] dp = new long[N + 1][M + 1];
        // 세로 공사중
        long[][] prohibitRow = new long[N + 1][M + 1];
        // 가로 공사중
        long[][] prohibitCol = new long[N + 1][M + 1];

        for(int i = 0; i < forbidCount; i++){
            int[] rowAndCol = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            if(rowAndCol[1] == rowAndCol[3]) {
                prohibitRow[Math.min(rowAndCol[0],rowAndCol[2])][rowAndCol[1]] = 1;
            }
            else{
                prohibitCol[rowAndCol[0]][Math.min(rowAndCol[1],rowAndCol[3])] = 1;
            }
        }

        //공사 시작 지점 까지 1로 초기화
        for(int i = 0; i <= N; i++){
            if(prohibitRow[i][0] == 1){
                dp[i][0] = 1;
                break;
            }
            dp[i][0] = 1;
        }

        //공사 시작 지점 까지 1로 초기화
        for(int i = 0; i <= M; i++){
            if(prohibitCol[0][i] == 1){
                dp[0][i] = 1;
                break;
            }
            dp[0][i] = 1;
        }

        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M ; j++){
                // 위 왼쪽 둘다 공사중 인경우
                if(prohibitRow[i-1][j] == 1 && prohibitCol[i][j-1] == 1) dp[i][j] = 0;
                // 위쪽만 공사중 인경우
                else if(prohibitRow[i-1][j] == 1) dp[i][j] = dp[i][j-1];
                // 왼쪽만 공사중 인경우
                else if(prohibitCol[i][j-1] == 1) dp[i][j] = dp[i-1][j];
                // 공사중 아닐 경우
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        System.out.println(dp[N][M]);
    }
}