[백준] 17070. 파이프 옮기기 1

문제

https://www.acmicpc.net/problem/17070





풀이

문제의 조건이 좀 애매한데, 그 자리에서 돌려도 되는 것인지, 무조건 이동하면서 회전해야 하는지 정확히 명시하지 않아서 헷갈렸다. 파이프는 이동하면서 회전하기 때문에 그림에 나온 7가지의 경우만 생각해주면 된다. 이 때 색칠한 칸에는 벽이 없어야 하며, 맵의 안쪽이어야 한다.
문제가 (n, n)에 도달할 수 있는 경우의 수이므로 DFS로 푸는게 더 직관적이라고 생각한다. 현재 위치에서 갈 수 있는 모든 방향에 대하여 DFS를 돌려서 모든 방법을 탐색하면 된다. 특히 카카오 문제의 경우 뒤쪽도 도 마음대로 회전할 수 있어서 앞, 뒤의 구분이 없지만, 이 문제는 미는 방향이 오른쪽, 아래쪽, 대각선쪽으로 밀 수 있으므로 뒤쪽이 앞쪽보다 (n, n) 좌표에 더 가까이 갈 수 있는 경우는 없다. 또한 뒤쪽의 좌표는 어떻게 밀어도 항상 앞쪽의 원래 이전 좌표로 이동하기 때문에 결과적으로 앞쪽에 대해서만 좌표 체크를 하면 된다. 즉, 뒤쪽 파이프는 앞쪽과 비교해서 가로 모양인지, 세로 모양인지, 대각선 모양인지 파악하기 위한 용도라고 보면 되겠다.
카카오 2020 블라인드 테스트에 이 문제처럼 2개의 좌표를 차지하는 문제가 있었는데, 그건 모든 경우에 대해 회전해야 해서 좀 더 어려웠는데, 이 문제는 상대적으로 더 쉬웠던 것 같다.
마지막으로 이번에도 역시 좌표는 (y, x) 이다. x, y의 좌표에 항상 주의하자.

//
//  17070.cpp
//  BJ
//
//  Created by 신기열 on 12/11/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

int map[17][17];
int n, answer;

void DFS(pair<pair<int, int>, pair<int, int> > p){
    
    int bx = p.first.first, by = p.first.second, fx = p.second.first, fy = p.second.second;
    
    // 앞 파이프 좌표가 (n,n) 이면 가능 횟수 + 1 하고 끝낸다.
    if(fx == n && fy == n){
        answer++; return;
    }
    
//    int tmap[17][17];
//
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= n; j++){
//            tmap[i][j] = map[i][j];
//        }
//    }
//    tmap[by][bx] = 2; tmap[fy][fx] = 2;
//
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= n; j++){
//            cout << tmap[i][j] << " ";
//        }
//        cout << '\n';
//    }
//    cout << '\n';
    
    
    // 세로 방향
    if(bx == fx && fy == by + 1){
        for(int i = 0; i < 2; i++){
            // 세로 방향으로만 미는 방법
            if(i == 0){
                // 그림에 나온 방향에 벽이 없고 맵 안에 있으면
                if(fy + 1 <= n && map[fy + 1][fx] == 0){
                    DFS(make_pair(make_pair(bx, by + 1), make_pair(fx, fy + 1)));
                }
            }
            // 세로 방향으로 밀고 대각선으로 회전
            else if(i == 1){
                // 그림에 나온 방향에 벽이 없고 맵 안에 있으면
                if(fx + 1 <= n && fy + 1 <= n && map[fy][fx + 1] == 0 && map[fy + 1][fx + 1] == 0 && map[fy + 1][fx] == 0){
                    DFS(make_pair(make_pair(bx, by + 1), make_pair(fx + 1, fy + 1)));
                }
            }
        }
    }
    // 가로 방향도 역시 마찬가지
    else if(by == fy && fx == bx + 1){
        for(int i = 0; i < 2; i++){
            if(i == 0){
                if(fx + 1 <= n && map[fy][fx + 1] == 0){
                    DFS(make_pair(make_pair(bx + 1, by), make_pair(fx + 1, fy)));
                }
            }
            else if(i == 1){
                if(fx + 1 <= n && fy + 1 <= n && map[fy][fx + 1] == 0 && map[fy + 1][fx] == 0 && map[fy + 1][fx + 1] == 0){
                    DFS(make_pair(make_pair(bx + 1, by), make_pair(fx + 1, fy + 1)));
                }
            }
        }
    }
    // 대각선 방향
    else if(fx == bx + 1 && fy == by + 1){
        for(int i = 0; i < 3; i++){
            if(i == 0){
                if(fy + 1 <= n && map[fy + 1][fx] == 0){
                    DFS(make_pair(make_pair(bx + 1, by + 1), make_pair(fx, fy + 1)));
                }
            }
            else if(i == 1){
                if(fx + 1 <= n && map[fy][fx + 1] == 0){
                    DFS(make_pair(make_pair(bx + 1, by + 1), make_pair(fx + 1, fy)));
                }
            }
            else if(i == 2){
                if(fx + 1 <= n && fy + 1 <= n && map[fy][fx + 1] == 0 && map[fy + 1][fx] == 0 && map[fy + 1][fx + 1] == 0){
                    DFS(make_pair(make_pair(bx + 1, by + 1), make_pair(fx + 1, fy + 1)));
                }
            }
        }
    }
}


int main(){
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> map[i][j];
        }
    }
    DFS(make_pair(make_pair(1, 1), make_pair(2, 1)));
    cout << answer;
    return 0;
}