[백준] 17069 : 파이프 옮기기 2 (JAVA/자바)

문제

BOJ 17069 : 파이프 옮기기 2 - https://www.acmicpc.net/problem/17069

풀이

파이프 옮기기 1에서는 N의 범위가 (3 ≤ N ≤ 16)이어서 BFS로 풀이해도 됐는데, 2에서는 N의 범위가 (3 ≤ N ≤ 32)이어서 시간초과가 난다. DP로 풀이했다!

놓여있는 방향에 따라 가로일 경우, 세로일 경우, 대각선일 경우로 나누어 dp 테이블을 채우면 된다.

• dp[i][j][d] : i,j 위치에 d 방향으로 파이프가 도달할 수 있는 방법의 경우의 수

(이미지 출처 : https://rebas.kr/838)

위 그림처럼 파이프가 움직일 수 있는 경우를 생각해볼 수 있다. 이것을 코드로 표현하면 다음과 같다.

• dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2]
• dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2]
• dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]

최종적으로 답은 dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2] 이 된다!

코드

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

public class Main {

    static int[][] map;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(inputs[j-1]);
            }
        }

        if(map[n][n]==1){
            System.out.println(0);
            return;
        }

        long[][][] dp = new long[n+1][n+1][3];
        dp[1][2][0] = 1; // initialize


        // DP
        for (int i = 1; i <= n; i++) {
            for (int j = 3; j <= n; j++) {
                if(map[i][j]==1) continue;

                // 가로 (0)
                dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2];

                if(i==1) continue; // 맨 윗줄이면 continue

                // 세로 (1)
                dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2];

                if(map[i-1][j]==1 || map[i][j-1]==1) continue;

                // 대각선 (2)
                dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
            }
        }

        System.out.println(dp[n][n][0]+dp[n][n][1]+dp[n][n][2]);
    }
}

정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍
✔ 난이도 - 🟡 Gold 5

🤦‍♀️ 오늘의 메모

• DP는 넘 어렵따,,,
• 이렇게 dp를 3중 배열로 만들어서 풀이하는 경우가 꽤 있는 것 같다. 잘 알아두기!

참고 사이트

https://gre-eny.tistory.com/312