[JAVA] 백준 17070 - 파이프 옮기기 1

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

2칸을 차지하는 파이프를 끝점까지 옮기는 방법의 가짓수를 구하는 문제이다.

파이프를 옮기는 방법은 가로 이동, 세로 이동, 대각선 이동의 3가지가 있는데, 가로로 이동했을 때는 가로 이동과 대각선 이동만 가능하고, 세로 이동의 경우는 세로, 대각선 이동, 대각선은 모든 이동이 가능하다는 제약조건이 있다.

 

N * N 배열의 요소는 0과 1인데, 1은 벽으로 이동이 불가능한 구간이다.

 

처음에는 DFS를 이용한 완전탐색으로 가능한 모든 이동요소를 구해 i,j 메모이제이션 배열에 도착횟수를 1씩 더하도록 구현했는데 16 * 16 배열에서 시간초과가 터졌다.

 

그래서 i * j * 3의 메모이제이션 배열을 사용해서 각 칸별, 도착 방법별 배열을 구현하고 DP로 풀었다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a = Integer.parseInt(br.readLine());
        int[][] map = new int[a][a];
        for (int i = 0; i < a; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        int[][][] memo = new int[a][a][3];
        memo[0][1][0] = 1; //[0,1]에서 파이프는 가로모양밖에 존재하지 않음
        for (int i = 0; i < a; i++) {
            for (int j = 2; j < a; j++) {
                if (map[i][j] == 1) continue;
                memo[i][j][0] = memo[i][j - 1][0] + memo[i][j - 1][2]; // [i, j]에 가로로 도달하려면 [i, j-1]에 가로로 도달하거나, [i,j-1]에 대각선으로 도달해야 접근가능 
                if (i > 0) {
                    memo[i][j][1] = memo[i - 1][j][1] + memo[i - 1][j][2]; // [i, j]에 세로로 도달하려면 [i-1, j]에 세로로 도달하거나, [i-1,j]에 대각선으로 도달해야 접근가능 
                    if (map[i][j - 1] == 0 && map[i - 1][j] == 0 && map[i - 1][j - 1] == 0) { // 대각선 이동이 가능하려면 [i, j-1], [i-1,j], [i-1,j-1]에 벽이 없어야 한다.
                        memo[i][j][2] = Arrays.stream(memo[i - 1][j - 1]).sum();//[i-1, j-1]에 어떤 방법으로 접근했든 대각선으로 [i,j]에 접근 가능하므로 배열의 합
                    }
                }
            }
        }

        System.out.println(Arrays.stream(memo[a - 1][a - 1]).sum()); //배열의 끝칸의 도달하는 가짓수의 합
    }
}

사실 GPT한테 DFS 썼다고 엄청 혼났다. 

DP 점화식 떠올리는 게 너무 어려운 것 같다.