[백준 - 17070] 파이프 옮기기 1 - C++

분류: DP, DFS /

 

문제

문제 링크

문제 설명

유현이가 새 집으로 이사했다. 새 집의 크기는 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보다 작거나 같다.

 

풀이

- DFS

#include <iostream>
#include <vector>
using namespace std;

int N, ans;
bool isWall[17][17];
int dx[] {0, 1, 1}; // direction -> delta position
int dy[] {1, 1, 0}; // direction -> delta position
vector<int> nxt[] {{0, 1}, {0, 1, 2}, {1, 2}}; // direction -> next directions
vector<int> check[] {{0}, {0, 1, 2}, {2}}; // next direction -> directions should be checked

inline bool isValid(int x, int y) {
    return x < N and y < N and not isWall[x][y];
}

void dfs(int dir, int x, int y) {
    if(x == N-1 and y == N-1) {
        ans++;
        return;
    }

    for(int nd:nxt[dir]) {
        int nx = x + dx[nd], ny = y + dy[nd];
        if(not isValid(nx, ny)) continue;
        
        bool pass = true;
        for(int d:check[nd]) {
            if(isValid(x + dx[d], y + dy[d])) continue;
            pass = false;
            break;
        }

        if(not pass) continue;
        dfs(nd, nx, ny);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> isWall[i][j];
    
    dfs(0, 0, 1);
    cout << ans;
}

DFS로 완전탐색

가로 방향을 0, 대각선 방향을 1, 세로 방향을 2로 정의

`nxt[i]`는 `i`방향으로 이동해서 `(x, y)`왔을 때, `(x, y)`에서 이동할 수 있는 다음 방향을 의미

`check[i]`는 `i`방향으로 이동하기 위해 확인해야하는 방향을 의미

`dfs(dir, x, y)`는 `dir` 방향으로 이동해 `(x, y)`에 도착했을 때 다음 이동을 DFS로 탐색하는 함수

 

`dfs()`를 살펴보면 아래와 같다.

• 종료 조건: 목적지 `(N-1, N-1)` 도착할 경우 경로 수 1 증가(`ans++`)
• `(x, y)`로 들어온 방향(`dir`)에 따라 다음에 갈 수 있는 방향(`nxt[dir]`)으로 다음을 수행
  • 다음 방향(`nd`)으로 갈 때, 확인해야 하는 방향(`check[nd]`)으로 모두 갈 수 있는 지 확인
  • 갈 수 있다면 해당 방향(`nd`)로 이동하고 재귀 호출

 

- DP

#include <iostream>
using namespace std;

int N;
bool isWall[17][17];
int way[17][17][3];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            cin >> isWall[i][j];
    
    way[1][2][0] = 1;
    for(int x=1; x<=N; x++) {
        for(int y=1; y<=N; y++) {
            if(isWall[x][y]) continue;
            way[x][y][0] += way[x][y-1][0] + way[x][y-1][1];
            way[x][y][2] += way[x-1][y][1] + way[x-1][y][2];
            if(isWall[x-1][y] or isWall[x][y-1]) continue;
            way[x][y][1] += way[x-1][y-1][0] + way[x-1][y-1][1] + way[x-1][y-1][2];
        }
    }
    cout << way[N][N][0] + way[N][N][1] + way[N][N][2];
}

처음 DFS로 풀었을 때 시간은 152ms. 보통 0ms ~ 20ms 사이의 시간이 나와야 마음이 편안해 지는데 152ms는 뭔가 느리다고 생각해 더 빠른 풀이를 더 생각해 봤다.

 

DFS 탐색보다 빠른 완전탐색을 생각해보면 백트래킹, 분기한정 등을 이용한 프루닝을 통해 탐색 범위를 좁히는 방법(시간 복잡도는 거의 같다)들과 DP 정도가 떠올랐다.

`way[x][y][dir]`은 `(x, y)`에서 `dir` 방향으로 들어오는 경로의 수다.

따라서 `way[x][y][0] = way[x][y-1][0] + way[x][y-1][1]`의 의미는 가로 방향으로 `(x, y)`에 들어오는 경로(`way[x][y][0]`)는 가로방향으로 `(x, y-1)`에 도착한 경우(`way[x][y-1][0]`)와 대각선 방향으로 `(x, y-1)`에 도착한 경우(`way[x][y-1][1]`)의 합과 같다.

 

마지막의 `way[x][y][1]`의 경우 대각선으로 들어오는 경우를 의미하고 이 경우에는 추가적으로 주변에 벽이 있는지 확인해야 한다.

 

등호가 아닌 `+=`로 기존 값에 더하는 이유는 초기값 때문이다. 논리적으로는 등호가 알맞다. 하지만 등호로 구현할 경우 초기값인 `way[1][2][0]`이 덮어쓰여지지 않도록 추가적인 작업이 필요하다. 어차피 초기화된 값이 0이므로 추가적인 작업을 구현하지 않기 위해 `+=`로 구현했다.