[boj] 백준 17070 파이프 옮기기 1 (c++) - DFS

[문제]

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

17070번: 파이프 옮기기 1

 

[풀이]

DFS 문제로 가로, 세로, 대각선 이동 시 파이프 끝이 차지하는 좌표를 dr, dc 배열에 저장해서 이동을 시켜준다.

이때 추가적으로 고려해주어야 하는 상황은 다음과 같다.

1. 세로로 놓여져있으면 가로 방향으로, 가로로 놓여져있으면 세로 방향으로 이동할 수 없다. 따라서 dir을 추가적으로 전달해줘서 이와 같은 케이스를 막는다.

2. 아래 사진과 같이, 대각선 이동 시 이동하는 파이프 끝 좌표 (nr, nc) 뿐 아니라 (nr-1, nc), (nr, nc-1) 역시 벽이 아니어야 한다.  

 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n;
int house[17][17];
int dr[3] = {0, 1, 1};
int dc[3] = {1, 0, 1}; //가로, 세로, 대각선
int ans = 0;

void dfs(int r, int c, int dir){
    if(r==n && c==n){
        ans++;
        return;
    }
    for(int i=0; i<3; i++){
        if((dir==1 && i==0) || (dir==0 && i==1)) continue; //세로->가로, 가로->세로 이동 못 함.

        int nr = r + dr[i];
        int nc = c + dc[i];

        if(nr<1 || nc<1 || nr>n || nc>n || house[nr][nc]) continue;

        //대각선 이동 시 벽 고려
        if(i==2 && (house[nr-1][nc] || house[nr][nc-1])) continue;

        dfs(nr, nc, i);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> house[i][j];
        }
    }

    dfs(1, 2, 0); // dir 0: 가로, 1: 세로, 2: 대각선
    cout << ans;

}