도로의 개수 - 백준 1577 (Java)

 

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

 

풀이

 

 먼저 아무 조건없이 격자 맵을 이동할 때 각 꼭지점마다 도달할 수 있는 경우의 수를 적어서 최종 목적지까지 도달하는 경우의 수를 구하는 방법을 생각했다. 이동 방향이 왼쪽 아래에서 오른쪽 위로 이동하기 때문에 현재 자신의 왼쪽 지점과 아래 지점까지 도달한 경우의 수의 합을 적어주면 된다.

 

 

 여기서 이동할 수 없는 도로가 생겼을 땐, 해당 도로를 이동해야 자신에게 도착하는 경우의 수를 더하지 않으면 된다. 만일 왼쪽과 아래 점에서 오는 도로를  둘 다 이용하지 못할 경우 해당 지점에 도착하는 경우의 수는 0이 된다.

 

 

 이를 코드에 옮기기 위해서, 꼭지점과 도로에 대한 정보를 담을 배열이 둘 다 필요했다. 그래서 꼭지점에 대한 이차원 배열 (long[][] dp)를 만들었다. 각 꼭지점에는 해당 꼭지점에 도착할 수 있는 경우의 수를 기록했다. 도로에 대한 이차원 배열은 가로 도로(int[][] horizontal)와 세로 도로(int[][] vertical)를 나눠서 만들었다. 부실공사로 이용하지 못하는 도로는 1로, 이용 가능한 도로는 0으로 초기화를 해줬다.

 

    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    //점 배열
    long[][] dp = new long[N+1][M+1];

    //선 배열 (1 : 부실공사)
    //가로 선
    int[][] horizontal = new int[N][M+1];
    //세로 선
    int[][] vertical = new int[N+1][M];

    int K = Integer.parseInt(bf.readLine());

    for (int i = 0; i < K; i++) {
        st = new StringTokenizer(bf.readLine(), " ");
        int x1 = Integer.parseInt(st.nextToken());
        int y1 = Integer.parseInt(st.nextToken());
        int x2 = Integer.parseInt(st.nextToken());
        int y2 = Integer.parseInt(st.nextToken());

        if (y1==y2) {
            //가로 도로
            horizontal[Math.min(x1, x2)][y1] = 1;
        } else {
            //세로 도로
            vertical[x1][Math.min(y1, y2)] = 1;
        }//if~else end
}//for end

 

 

 본격적으로 이동하기 전, 가로 0 혹은 세로 0에 해당하는 지점을 1로 초기화해줬다. 만일, 부실공사 도로가 있다면 해당 도로 이후의 지점은 모두 0으로 그대로 둔다.

 

//가로 (세로값 0인 지점) 1로 초기화
for (int i = 1; i <= N; i++) {
    //부실공사 도로면 그 뒤 다 0으로 초기화
    if (horizontal[i-1][0] == 1) break;

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

//세로 (가로값 0인 지점) 1로 초기화
for (int i = 1; i <= M; i++) {
    //부실공사 도로면 그 뒤 다 0으로 초기화
    if (vertical[0][i-1] == 1) break;

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

 

 

 본격적으로 이동하면서 각 꼭지점에 도달할 수 있는 경우의 수를 기록한다. 해당 꼭지점의 왼쪽 꼭지점과 아래 꼭지점에 도착하는 경로의 수를 합치면 된다. 만일 이 두 지점에서 해당 꼭지점까지의 도로가 부실공사라면 빼준다.

 

최종적으로 마지막 지점을 출력해주면 된다.

 

//이동
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];

        //가로 도로 부실공사 여부
        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 end
}//for end

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