[Java] 백준 1577 (도로의 개수)

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

1577번: 도로의 개수

알고리즘 분류

• 다이나믹 프로그래밍(dp)

 

 

풀이

처음에 dfs로 문제를 풀어야 되나 싶었지만 범위를 보고 dp문제임을 깨달았다.

 

먼저 초기화 작업이다. 

가짓수를 저장하는 2차원 배열 dp이다. int형으로는 표현하기 어렵기때문에 long형으로 선언했다.

그리고 세로로 공사중인 곳을 저장하기 위한 horizontal,

가로로 공사중인 곳을 저장하귀 위한 vertical 배열을 선언해줬다.

long [][] dp = new long[n+1][m+1];

//가로 선
int[][] horizontal = new int[n][m+1];

//세로 선
int[][] vertical = new int[n+1][m];

 

 

입력을 받으면서 공사중인 길이 세로로 있는지 가로로 있는지 체크 후( if (b == d){} )

y값이 같으면 가로 길이므로 horizontal에 

x값이 같으면 세로 길이므로 vertical에

더 작은값 좌표에다가 1을저장하였다.

 for (int i = 0; i < k; i++) {
            // init
     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){
        horizontal[Math.min(a, c)][b] = 1;
     }else{
         ertical[a][Math.min(b, d)] = 1;
     }

} // for

 

 

 

그 다음 제일 밖에 있는 길의 경우의 수를 먼저 초기화 하는 작업이다.

제일 밖에 있는 길은 1가지 밖에 없으므로 1을 배열에 넣는다.

아래의 그림을 보면 더 이해하기 편할 것이다.

X라는 길이 공사중이라고 가정했을 때 문제에서 돌아가는 경우는 없다고 하니 더이상 갈 수 있는 경우의 수는 없다.

// 제일 밖에 있는 가로 길 초기화
for (int i = 1; i < n+1; i++) {
     if (horizontal[i-1][0] == 1) break;
     dp[i][0] = 1L;

} // for

// 제일 밖에 있는 세로 길 초기화
for (int i = 1; i < m+1; i++) {
     if (vertical[0][i-1] == 1) break;
     dp[0][i] = 1;
} // for

 

 

그래서 공사중인 길이 있으면 더이상 갈 수 있는 경우의 수가 없기때문에 break문을 추가 하였다.

 

 

 

 

이제 학교로 가는 길 경우의 수가 총 몇개 있는지  구한다.

 

아래의 그림으로 설명하자면 갈려는 곳의 길 경우의 수를 구하면

왼쪽의 길 경우의 수와 위쪽길의 길 경우의 수를 합하면 된다.

따라서 이걸 DP를 이용해 2차원 배열에서 [x-1][y] + [x][y-1]로 경우의 수를 구했다. 

하지만 만약 그 길이 공사중이면 그쪽에서 오는 경우의 수는 없기 때문에 

다시 빼주는 조건문도 추가하였다.

for (int i = 1; i < dp.length; i++) {
    for (int j = 1; j < dp[0].length; j++) {
    dp[i][j] = dp[i][j-1] + dp[i-1][j]; // dp로 길 경우의 수 구한다.

	// 가로 길이 공사중이면 다시 빼준다.
    if (horizontal[i-1][j] == 1) {
       dp[i][j] -= dp[i-1][j];
    }

    //세로 길이 공사중이면 다시 빼준다.
    if (vertical[i][j-1] == 1) {
       dp[i][j] -= dp[i][j-1];
    }
    
    } // for
} // for

 

 

 

 

아래는 전체 정답 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[][] horizontal = new int[n][m+1];
        //세로 선
        int[][] vertical = new int[n+1][m];

        int k = Integer.parseInt(br.readLine());
        for (int i = 0; i < k; i++) {
            // init
            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){
                horizontal[Math.min(a, c)][b] = 1;
            }else{
                vertical[a][Math.min(b, d)] = 1;
            }

        } // for

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

            dp[i][0] = 1L;

        } // for
        for (int i = 1; i < m+1; i++) {

            if (vertical[0][i-1] == 1) break;

            dp[0][i] = 1;
        } // for

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];

                if (horizontal[i-1][j] == 1) {
                    dp[i][j] -= dp[i-1][j];
                }

                //세로 도로 부실공사 여부
                if (vertical[i][j-1] == 1) {
                    dp[i][j] -= dp[i][j-1];
                }
            } // for
        } // for
        System.out.println(dp[n][m]);

    } // main
}