[Algorithm] 백준_17070 파이프 옮기기 1

문제

유현이네 집을 N*N 격자판으로 나타내고, 한 칸을 (r, c)라고 했을 때 두 칸에 걸쳐 파이프가 있다. 파이프는 가로, 세로, 대각선 방향으로 옮길 수 있고 밀면서 회전이 가능하다.
처음의 파이프가 (1, 1) (1, 2)를 차지하고 있을 때 파이프의 한쪽 끝을 (N, N)로 이동시킬 방법의 개수를 구해야한다.

풀이

최소 경로가 아닌 모든 경로의 경우를 구해야하기 때문에 DFS로 풀이했다. DFS로 풀이한 후 시간을 좀 줄여보기 위해 DFS + DP로도 풀이해봤다!

3차원의 dp배열을 선언한다.

dp = new int[n+1][n+1][3];

맨 마지막 3번째 배열은 0은 가로, 1은 세로, 2는 대각선 방향으로 움직였을 경우의 수를 저장한다.

dfs에서는
1. map의 범위를 벗어났거나, map[x][y] == 1로 벽인 경우
2. 파이프의 방향이 대각선일때 map[x][y-1] 혹은 map[x-1][y]가 벽인 경우에는 진행할 수 없도록 했고,
3. dp[x][y][dir]에 값이 -1 (초기값)과 같지 않으면 그 값을 return
4. x와 y가 도착점일 때 1을 return
하도록 했다.

for문으로 파이프를 옮기는데, 가로 -> 세로, 세로 -> 가로로 옮길 수 없도록 했다.

if ((dir == 0 && i == 1) || (dir == 1 && i == 0)) continue;

소스 코드

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

public class BOJ_17070 {
    static int n;
    static int[][] map;
    static int[][][] dp;
    static int[] dx = {0, 1, 1}; //가, 세, 대
    static int[] dy = {1, 0, 1};
    static int count;

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

        map = new int[n+1][n+1];
        dp = new int[n+1][n+1][3];

        for (int i = 1; i <= n; i++) {
             st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }

        count = dfs(1, 2, 0);
        System.out.println(count);
    }

    // 가로 0
    // 세로 1
    // 대각선 2
    static int dfs(int x, int y, int dir) {
        if (x > n || y > n || map[x][y] == 1) {
            return 0;
        }

        if (dir == 2 && (map[x][y - 1] == 1 || map[x - 1][y] == 1)) {
            return 0;
        }

        if (dp[x][y][dir] != -1) {
            return dp[x][y][dir];
        }

        if (x == n && y == n) {
            return 1;
        }

        int sum =0;
        for (int i = 0; i < 3; i++) {
            if ((dir == 0 && i == 1) || (dir == 1 && i == 0)) {
                continue;
            }

            int nx = x + dx[i];
            int ny = y + dy[i];

            sum += dfs(nx, ny, i);
        }

        return dp[x][y][dir] = sum;
    }
}