BOJ 17070 - 파이프 옮기기 1

문제

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

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

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

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

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

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

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

가로

세로

대각선

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

이 문제는 단순 격자 경로 수 세기가 아니라 방향 상태가 있는 DP다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int N;
    static int result = 0;
    static int[][] map;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N + 1][N + 1];
 
        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());
            }
        }
 
        solve(1, 2, 1);
        System.out.println(result);
    }
 
    // dir - 1:가로 / 2:세로 / 0:대각선
    static void solve(int x, int y, int dir) {
        if (x == N && y == N) {
            result++;
            return;
        }
 
        if (dir == 0) {
            checkAndDeploy(x, y + 1, 1);
            checkAndDeploy(x + 1, y, 2);
            checkAndDeploy(x + 1, y + 1, 0);
        } else if (dir == 1) {
            checkAndDeploy(x, y + 1, 1);
            checkAndDeploy(x + 1, y + 1, 0);
        } else if (dir == 2) {
            checkAndDeploy(x + 1, y, 2);
            checkAndDeploy(x + 1, y + 1, 0);
        }
    }
 
    static void checkAndDeploy(int nx, int ny, int dir) {
        if (nx > N || ny > N) {
            return;
        }
 
        if (dir == 0) {
            if (map[nx][ny] == 0 && map[nx - 1][ny] == 0 && map[nx][ny - 1] == 0) {
                solve(nx, ny, dir);
            }
        } else {
            if (map[nx][ny] == 0) {
                solve(nx, ny, dir);
            }
        }
    }
}

복잡도

시간 복잡도: $O(N^2)$ 또는 상태 수만큼
공간 복잡도: $O(N^2)$

마무리

파이프 문제의 핵심은 좌표 하나가 아니라 방향까지 상태에 들어간다는 점이다. 방향별 이동 가능 조건을 분리해서 보면 점화식이 깔끔해진다.

BOJ 17070 - 파이프 옮기기 1

문제

입력

출력

풀이

코드

복잡도

마무리

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리