[백준 / Java] 17070번 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

문제 유형

• 다이나믹 프로그래밍
• DFS

 

문제 풀이

이 문제는 DFS(깊이 우선 탐색) 과 다이나믹 프로그래밍 으로 각각 해결할 수 있다.

 

DFS

DFS 를 이용한 풀이 방법은 매우 간단하다.
별도의 방문처리 배열을 사용하지 않고, 조건에 맞게 재귀를 수행하면 된다.
이런 점에서 재귀를 이용한 구현 문제에 더 가깝다고 할 수도 있다.

 

소스 코드

import java.util.*;
import java.io.*;

class Main {

    int n;
    int[][] arr = new int[16][16];
    int answer = 0;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 1, 0);

        System.out.println(answer);
    }

    public void dfs(int x, int y, int direction) {
        if (x == n - 1 && y == n - 1) {
            answer++;
            return;
        }

        if (direction == 0) {
            if (y + 1 < n && arr[x][y + 1] == 0) dfs(x, y + 1, 0);
        } else if (direction == 1) {
            if (x + 1 < n && arr[x + 1][y] == 0) dfs(x + 1, y, 1);
        } else {
            if (y + 1 < n && arr[x][y + 1] == 0) dfs(x, y + 1, 0);
            if (x + 1 < n && arr[x + 1][y] == 0) dfs(x + 1, y, 1);
        }

        if (x + 1 < n && y + 1 < n && arr[x][y + 1] == 0 && arr[x + 1][y] == 0 && arr[x + 1][y + 1] == 0) dfs(x + 1, y + 1, 2); 
    }
}

 

다이나믹 프로그래밍

이 문제를 DFS 대신 BFS 를 이용하여 풀면, 시간초과가 발생하는 경우가 있다고 한다.
그래서 다이나믹 프로그래밍 을 이용하여 시간초과로부터 안전하게 문제를 해결해야 한다.

다이나믹 프로그래밍 을 이용하기 위해서는 먼저 점화식을 세워야 한다.
파이프의 방향은 오른쪽, 아래, 대각선 총 3가지 이므로,

파이프의 방향을 포함한 파이프의 끝 값의 위치까지 이동한 횟수를 저장할 3차원 dp 배열을 먼저 선언해야 한다.

dp[행(N)][열(N)]][파이프의 방향(3)]
- dp[n][n][0] : 오른쪽 방향의 파이프의 끝 지점이 (n, n)
- dp[n][n][1] : 아래 방향의 파이프의 끝 지점이 (n, n)
- dp[n][n][2] : 오른쪽 대각선 방향의 파이프의 끝 지점이 (n, n)

각 파이프 방향마다 갈 수 있는 경우가 정해져 있기 때문에 이에 맞게 점화식을 세워주면 된다.

 

간단한 예로 서로 인접한 정사각형 모양의 4개의 칸을 살펴보자.

A(2, 2) B(2, 3)
C(3, 2) D(3, 3)

파이프 이동 후 D가 파이프의 끝 지점이 되는 경우는

D를 기준으로 위, 왼쪽, 왼쪽 대각선 위 지점을 각각 살펴보면 된다.

1) 위(B) : 아래, 대각선 방향으로 B가 끝 지점인 2개의 파이프에서 D로 이동할 수 있다.
2) 왼쪽(C) : 오른쪽, 대각선 방향으로 C가 끝 지점인 2개의 파이프에서 D로 이동할 수 있다.
1) 왼쪽 대각선 위(A) : 오른쪽, 아래, 대각선 방향의 A가 끝 지점인 3개의 파이프에서 D로 이동할 수 있다.

위의 방식대로 점화식을 세워보면 아래와 같다.

if (i, j) 지점이 벽이 아닐 때 :
    if (i, j - 1), (i - 1, j) 지점이 벽이 아닐 때 :
        dp[i][j][2] += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
    dp[i][j][1] += dp[i - 1][j][1] + dp[i - 1][j][2];
    dp[i][j][0] += dp[i][j - 1][0] + dp[i][j - 1][2];

문제에서 파이프가 이동할 때 꼭 빈 칸이어야 하는 곳이 주어져 있으므로,
이를 예외 조건으로 꼭 빼먹지 말고 점화식을 작성해야한다.

 

소스 코드

import java.util.*;
import java.io.*;

class Main {

    int n;
    int[][] arr = new int[17][17];
    int[][][] dp = new int[17][17][3];    // 0:오른쪽, 1:왼쪽, 2:대각선

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[1][2][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] == 1) continue;

                // 1) 왼쪽 대각선 위 기준
                if (arr[i - 1][j] == 0 && arr[i][j - 1] == 0) {
                    dp[i][j][2] += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
                }
                // 2) 위 기준
                dp[i][j][1] += dp[i - 1][j][1] + dp[i - 1][j][2];
                // 3) 왼쪽 기준
                dp[i][j][0] += dp[i][j - 1][0] + dp[i][j - 1][2];
            }
        }

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