[백준/BOJ] 17070번 파이프 옮기기 (C++)

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

삼성 A형 기출문제 : DFS

 

파이프는 오른쪽, 아래, 대각선 아래로 이동할 수 있고, 파이프가 놓여있는 경우에 따라 취할 수 있는 액션이 달라집니다.

 

파이프가 가로로 놓여있는 경우

오른쪽으로 이동

대각선 아래로 이동

 

파이프가 세로로 놓여있는 경우

아래로 이동

대각선 아래로 이동

 

파이프가 대각선으로 놓여있는 경우

오른쪽으로 이동

아래로 이동

대각선 아래로 이동

 

파이프의 움직임을 dx[], dy[] 배열을 만들어 저장해놓고, 파이프가 놓여있는 경우에 취하는 액션을 벡터를 만들어 저장합니다. 이것이 문제의 핵심이었습니다.

 

int dx[3] = {0, 1, 1}; // 0 : 오른쪽, 1 : 아래, 2 : 대각선 아래
int dy[3] = {1, 0, 1};
vector<int> action[3] = { {0, 2}, {1, 2}, {0, 1, 2} }; // 파이프 현재 방향에 따라 취할 수 있는 액션

 

파이프는 위에서 언급한 세 방향으로만 움직이기 때문에, DFS 탐색을 진행할 때 두개의 면에 해당하는 좌표를 넘겨줄 필요가 없습니다. 끝쪽에 있는 좌표만 넘겨줍니다. (0, 0), (0, 1) 로 처음 시작하므로 (0, 1) 을 시작점으로 DFS 탐색을 시작하면 됩니다.

 

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

int n, answer;
int map[17][17];
int dx[3] = {0, 1, 1}; // 0 : 오른쪽, 1 : 아래, 2 : 대각선 아래
int dy[3] = {1, 0, 1};
vector<int> action[3] = { {0, 2}, {1, 2}, {0, 1, 2} }; // 파이프 현재 방향에 따라 취할 수 있는 액션

void DFS(int x, int y, int type) {
    if(x == n - 1 && y == n - 1) {
        answer++;
        return;
    }
    
    for(auto it : action[type]) {
        int nx = x + dx[it];
        int ny = y + dy[it];
        
        if(nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == 1) continue;
        
        // 대각선 아래로 이동하는 경우 추가 체크
        if(it == 2 && (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)) continue;
        
        DFS(nx, ny, it);
    }
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    
    if(map[n - 1][n - 1] == 0) DFS(0, 1, 0);
    cout << answer;
}