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

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

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

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

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

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

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

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

 

가로

 

세로

 

대각선

 

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

---

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

public class Baekjoon17070_1 {
    static int n;
    static int[][] arr;
    static int count;

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

        n = Integer.parseInt(st.nextToken());
        arr = new int[n][n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        count = 0;
        pipe(0, 1, 0);
        System.out.println(count);
    }

    static int[] rotateP = {0, 1, 1};
    static int[] rotateQ = {1, 1, 0};

    public static void pipe(int p, int q, int d) {
        if(p == n - 1 && q == n - 1) {
            count++;
            return;
        }

        int i = 0, j = 0;

        if(d == 0) {            // 파이프 모양이 가로
            i = 0;
            j = 1;
        } else if (d == 1) {    // 파이프 모양이 대각선
            i = 0;
            j = 2;
        } else if(d == 2) {     // 파이프 모양이 세로
            i = 1;
            j = 2;
        }

        for(; i <= j; i++) {
            int np = p;
            int nq = q;
            np += rotateP[i];
            nq += rotateQ[i];

            if(np >= n || nq >= n) {
                // 벽 나가면 다른방향 찾음
                continue;
            }
            if(arr[np][nq] == 1) {
                // 가려는 방향에 벽이 있으면 다음 방향 찾음
                continue;
            }
            if(i == 1 && ((np - 1 >= 0 && arr[np - 1][nq] == 1) || (nq - 1 >= 0 && arr[np][nq - 1] == 1))) {
                // 대각선이었고 종착점 기준 왼쪽이나 위에 벽이 있으면 다음 방향 찾음
                continue;
            }

            pipe(np, nq, i);
        }
    }
}

 

델타 탐색과 재귀함수의 응용문제이다.

 

파이프의 모양에 따라서 진행 가능한 델타 탐색이 다르다.

 

파이프가 갈 수 있는 조건을 잘 맞추는게 중요하다.