[BOJ 17070] 파이프 옮기기2 [DP적 접근]

이 문제는 삼성 역량 테스트 기출문제입니다. 

당시 기억으로는 버스가 이동할 수 있는 경로의 가짓수를 구하라는 문제였는데.

놀랍게도 하루만에 복기돼서 버스가 파이프로 바뀌었던걸로 기억하고 있습니다. ㅋㅋ

그 때는 버스의 시작모양이 세로일 수도 있고 대각선일 수도 있었던 것 같은데.

이번 문제는 반드시 파이프(=버스)가 가로로 시작하네요~

여담이지만, 최근 이 문제의 제한시간을 0.5초로 줄였더군요! 그래서 더욱이 DP가 아니면 풀 수 없는 문제가 되고 말았습니다. 파이프1번 문제의 경우에는 BFS로 풀다 시간초과로 털리는 쓴맛을 보았기에,, 이해도 된 겸 포스팅으로 DP적 접근에 관한 아이디어를 나눠보겠습니다.

 

1). 점화식이란 무엇일까?

DP는 흔히, 점화식을 세운다라고 표현하곤 합니다.

...더보기

(동적계획법을 고안해낸 사람인 리차드 팔머는 자신의 자서전에 이렇게 말했다고 합니다. 당시 리차드씨가 연구를 하던 회사가 공군소속의 회사였고, 원래 이름을 multistage process 라고 지을려고 했다고 합니다. 그러나 process 라는 단어가 공군에서 쓰이는 용어였고 연구하기를 병적으로 싫어하던 그의 상사에게 자신이 연구하는 것을 들키지 않게 하기 위해서 process 대신 프로그래밍(계획법)을 쓰게 되었다고 하더군요. 그리고 시가변적으로 변하는 특성을 붙이기 위해 dynamic 이라는 표현을 써서 오늘날의 동적계획법이 되었다고 합니다.)

점화식은 이전의 항들의 값(인접항)을 알고 있을 때 이를 가지고 다음 항을 구해나갈 수 있는 모습이

심지에 불을 붙이는 것과 비슷하여 붙여진 이름이라고 합니다. 

(불이 한 번 붙기 시작하면 끄지 않는 이상 순식간에 번져나가듯이 말이죠!)

 

그리고 우리는 문제를 풀기위해, 즉 점화식을 세우기 위해서 인접항들 간의 규칙을 파악해낼 필요가 있습니다!

그럼, 규칙을 파악하러 당장가보죠 ㅎㅎ

cf). [(i, j) 에서 i는 행, j는 열을 의미합니다.]

이 문제에서는, (i,j)로 갈 수 있는 방법을 알고 있다면, (i,j)에서 가로, 세로, 대각선으로 가는 방향을 구할 수 있습니다.

그 말은 즉슨 (i,j)를 가로로 온 모든 경우 // 세로로 온 모든 경우// 대각선으로 온 모든 경우를 알고 있다는 뜻입니다.

그럼, 위에서 말한 인접항이 모두 구해진거로군요?! 이제 식을 세워볼까요?

 

인접항인 (i,j)을 사용해서 구할 수 있는 다음항은 다음과 같이 총 세가지가 있을 수 있겠습니다. 

1) 가로: 로 가는 경우는 (i,j+1) 로 가는 방법을 구하는 것이고~

2) 세로: 로가는 경우는(i+1, j)로 가는 방법을 구하는 것일겁니다.

3) 마찬가지로 대각선: 의 경우는 (i+1, j+1) 로 가는 방법을 구하는 거겠죠?!

 

이제 1), 2), 3) 을 구하는 식을 세워보죠!

1). (i, j)에서 가로로 가는 경우 = (i, j + 1) 을 구하는 것과 같습니다.

이는 (i, j) 를 가로 파이프로 도달한 경우 + (i, j) 를 대각선으로 도달한 경우 입니다.

왜냐하면 (i, j)에서 (i, j+1)로 갈 때 세로로 올 수는 없다고 문제에서 명시되어 있기 때문입니다.

자! 대신 우리가 구하려는 (i, j + 1) 지점은 범위 밖이거나, 벽(1)이면 안 됩니다! 이 또한 신경 써줘야할 부분입니다.

 

같은 방법으로,

2). (i, j) 에서 세로로 가는 경우 = (i + 1, j) 로 가는 경우를 구하는 것

이 때 역시 (i, j) 를 세로로 온 뒤 다시 세로로 (i + 1, j)로 가는 경우 +

(i, j) 를 대각선으로 온 뒤 다시 세로로 (i + 1, j)로 가는 경우 밖에 없다고 할 수 있겠습니다.

범위 검사또한 1)과 동일합니다.

 

마지막으로 대각선은

3). (i, j) 에서 대각선으로 가는 경우 = (i + 1, j + 1) 로 가는 경우를 구하는 것

(i, j)를 가로, 세로, 대각선으로 모두 올 수 있기 때문에 이 경우를 모두 더해야합니다.

다만, (i, j+1), (i+1, j)가 모두 범위 안에 있고 0이어야만 하겠습니다.

이해가 되셨을지 걱정이 됩니다... 적다보니 양이 만만치 않군요. 말로 설명하면 쉬울텐데.. ㅠ_ㅠ

말이 정말 길었는데. 여기까지 따라오셨다면 소스코드를 보면 금방 정리가 되실 겁니다. ㅎㅎ

궁금하신 건 댓글로 달아주세요 ^^

 

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

public class Main_파이프옮기기DP {
    static long[][][] dp; // N이 22정도면 40억 찍는다.
    static int[][] map;
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        map = new int[N+2][N+2];
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // dp[p][y][x]: p 모양으로 y,x에 도달할 수 있는 가짓수
        // →(i=0), ↓(i=1),↘(i=2)
        dp = new long[3][N+2][N+2];

        // 최초에 (1,1),(1,2)에는 → 방향으로 파이프가 놓여있고
        // → 방향은 dp[0] 일 때이다. 이곳도 길이 하나 있다고 초기화 해줘야 다음 값을 구해나갈 수 있다. ( 안 그러면 0으로만 채워지겠지? )
        dp[0][1][2] = 1;

        // dp[0,1,2][i][j] 값이(인접항) 이미 구해졌다고 생각하면, 이 값을 가지고 다음 값을 구할 수 있다.
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // (i,j)에서 가로로 갈 경우 = dp[0][i][j+1]
                if(map[i][j+1] == 0) // 벽인 경우엔 갈 수 없다.
                    dp[0][i][j+1] += dp[0][i][j] + dp[2][i][j];
                // 세로로 갈 경우
                if(map[i+1][j] == 0)
                    dp[1][i+1][j] += dp[1][i][j] + dp[2][i][j];
                // 대각선으로 갈 경우
                if(map[i][j+1] == 0 && map[i+1][j] == 0 && map[i+1][j+1] == 0)
                    dp[2][i+1][j+1] = dp[0][i][j] + dp[1][i][j] + dp[2][i][j];
            }
        }

        // 마지막으로 N,N에 0번 파이프로 온 경우 + 1로 온 경우 + 2로 온 경우을 다 더하면 된다~
        System.out.println(dp[0][N][N] + dp[1][N][N] + dp[2][N][N]);
    }
}