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

문제 링크: 17070번: 파이프 옮기기 1

 

 

난이도: 골드 5

 

 

소요시간: 40분

 

 

문제:

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

 

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

 

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

 

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

 

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

 

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

 

 

입력:

첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

 

 

출력:

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

 

문제 이해:

이 문제는 겉보기에는 단순해 보이지만, 파이프의 방향에 따라 이동 가능 경로가 달라진다는 점을 이해해야만 정확하게 해결할 수 있는 문제이다.

 

초기 상태에서는 파이프가 (1,1)과 (1,2)를 차지하며 가로 방향으로 놓여 있다. 이후 파이프를 가로, 세로, 대각선 방향으로 이동시키며 최종 목적지 (N,N)까지 도달할 수 있는 경우의 수를 구하는 것이 문제의 핵심이다.

 

특히 주의해야 할 점은 방향 전환 규칙이다.
가로 → 세로, 세로 → 가로로 직접 전환하는 것은 불가능하며, 반드시 대각선 이동을 통해서만 방향을 변경할 수 있다.
즉, 방향을 바꾸려면 중간에 대각선 배치가 필요하다는 제약 조건이 존재한다.

 

예를 들어, 다음과 같이 3×3 크기의 빈 공간일 경우:

3
0 0 0
0 0 0
0 0 0

이 경우 파이프는 처음 가로로 시작하므로 세로로 즉시 전환할 수 없고, 가능한 이동 경로는 다음 한 가지뿐이다.

• 가로 → 대각선 → 세로

따라서 이 상황에서의 경우의 수는 1가지가 된다.

 

 

구현 방향:

백준의 힌트에서는 이 문제가 동적 계획법(DP)을 이용해 해결할 수 있음을 명시하고 있었지만, 필자는 문제를 처음 접했을 때 DP 전환 구조를 직관적으로 도출하지 못해 DFS 기반의 백트래킹 방식으로 풀이하였다.

즉, 시작점부터 가능한 모든 방향으로 파이프를 이동시키며, 재귀적으로 탐색을 수행하고, 파이프의 끝이 (N, N)에 도달했을 때만 경우의 수로 누적하는 방식으로 문제를 해결하였다.

 

그러나 문제를 해결한 후 DP 접근 방식을 분석해보니 다음과 같은 메커니즘으로 이해할 수 있었다.

 

DP 메커니즘 요약

이 문제의 DP는 dp[x][y][d] 형태로 구성되며,
이는 파이프의 끝이 (x, y) 위치에 있고 방향이 d(0=가로, 1=세로, 2=대각선)일 때,
그 상태에 도달한 모든 경우의 수를 의미한다.

예를 들어,

dp[2][3][0] = 4

이라면, 이는 파이프가 (2,3)에 가로 방향으로 도달하는 방법이 4가지 존재한다는 의미이다.
DFS는 (2,3)에서 도착지까지 확장하는 방식이라면,
DP는 시작점에서 (2,3, 가로 방향)에 이르기까지의 모든 경로를 누적하며 확장해 나간다는 차이만 있을 뿐
결국 같은 결과를 도출하는 방식을 보다 효율적으로 수행하는 과정이라 할 수 있다.

 

이를 코드로 구현하면 다음과 같다.

 

 

정답 코드:

1)DFS 방식 코드

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

public class Main {
    static int N;
    static int[][] matrix;
    static int result=0;

    //pos 1:현재 가로방향, 2:현재 세로방향 3: 현재 대각선방향
    public static void solve(int x, int y, int pos){

        if(x==N-1 && y==N-1){
            result++;
            return;
        }

        //가로 배치가 가능한 경우
        if(pos!=2 && y+1<matrix[0].length && matrix[x][y+1]!=1){
            solve(x, y+1, 1);
        }

        //세로 배치가 가능한 경우
        if(pos !=1 && x+1<matrix.length && matrix[x+1][y]!=1){
            solve(x+1, y, 2);
        }

        //대각선 배치가 가능한 경우
        if(x+1<matrix.length && y+1<matrix[0].length
                && matrix[x+1][y+1]!=1 && matrix[x][y+1]!=1 && matrix[x+1][y]!=1){
            solve(x+1, y+1, 3);
        }
    }

    public static void main(String[] args) throws IOException {
        //초기세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());

        matrix=new int[N][N];

        for(int i=0; i<N; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                matrix[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        //초기 세팅 끝

        //파이프 시작위치 (0,1)
        solve(0,1,1);

        //결과 출력
        System.out.println(result);
    }
}

 

 

2) DP코드

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

public class Main {
    static int N;
    static int[][] board;
    static long[][][] dp; // dp[x][y][d] : (x,y)에 방향 d(0가로,1세로,2대각)로 도달하는 경우의 수

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

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

        dp = new long[N][N][3];

        // 초기 파이프: (0,0)~(0,1), 끝점 (0,1), 방향 가로(0)
        dp[0][1][0] = 1;

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (board[x][y] == 1) continue;

                // 가로 상태에서
                if (dp[x][y][0] > 0) {
                    // 가로 이동
                    if (y + 1 < N && board[x][y + 1] == 0) {
                        dp[x][y + 1][0] += dp[x][y][0];
                    }
                    // 대각 이동
                    if (x + 1 < N && y + 1 < N
                            && board[x][y + 1] == 0
                            && board[x + 1][y] == 0
                            && board[x + 1][y + 1] == 0) {
                        dp[x + 1][y + 1][2] += dp[x][y][0];
                    }
                }

                // 세로 상태에서
                if (dp[x][y][1] > 0) {
                    // 세로 이동
                    if (x + 1 < N && board[x + 1][y] == 0) {
                        dp[x + 1][y][1] += dp[x][y][1];
                    }
                    // 대각 이동
                    if (x + 1 < N && y + 1 < N
                            && board[x][y + 1] == 0
                            && board[x + 1][y] == 0
                            && board[x + 1][y + 1] == 0) {
                        dp[x + 1][y + 1][2] += dp[x][y][1];
                    }
                }

                // 대각 상태에서
                if (dp[x][y][2] > 0) {
                    // 가로 이동
                    if (y + 1 < N && board[x][y + 1] == 0) {
                        dp[x][y + 1][0] += dp[x][y][2];
                    }
                    // 세로 이동
                    if (x + 1 < N && board[x + 1][y] == 0) {
                        dp[x + 1][y][1] += dp[x][y][2];
                    }
                    // 대각 이동
                    if (x + 1 < N && y + 1 < N
                            && board[x][y + 1] == 0
                            && board[x + 1][y] == 0
                            && board[x + 1][y + 1] == 0) {
                        dp[x + 1][y + 1][2] += dp[x][y][2];
                    }
                }
            }
        }

        long result = dp[N - 1][N - 1][0] + dp[N - 1][N - 1][1] + dp[N - 1][N - 1][2];
        System.out.println(result);
    }
}

 

 

마무리하며:

이번 문제를 통해 DP 접근 방식의 장점과 사고 전환의 필요성을 다시 한 번 체감할 수 있었다. 아직 DP에 대한 이해와 점화식 도출 능력이 부족하다고 느끼지만, 다양한 유형의 문제를 접하며 경험을 쌓는다면 점차 익숙해질 것이라 생각한다.

 

 

감사합니다.