백준 17070번, 파이프 옮기기 1(C, C++)

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

17070번: 파이프 옮기기 1

#include<iostream>

using namespace std;

int N;
int map[18][18];
int cnt;

int dx[3] = {0, 1, 1}; // 가로, 세로, 대각선
int dy[3] = {1, 0, 1};
void dfs(int x, int y, int kind){

    if(x == N && y == N){
        cnt++;
        return;
    }

    for(int i = 0; i < 3; i++){
        if((i == 0 && kind == 1) || (i == 1 && kind == 0)){
            continue;
        }

        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny>N || nx>N || map[nx][ny] == 1){
            continue;
        }

        if(i == 2 && (map[x+1][y] == 1 || map[x][y+1] == 1)){
            continue;
        }
        dfs(nx, ny, i);
    }
}


int main(){
    cin>>N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <=N; j++){
            cin>>map[i][j];
        }
    }

    dfs(1, 2, 0);
    cout<<cnt;
    return 0;
}

 

DFS로 가로, 세로, 대각선으로 가는 방법을 구현하였습니다.

다만, 몇가지 제한 되는 경우가 있는데, 가로에서 세로가 나오는 경우와 세로에서 가로가 나오는 경우

그리고 맵 바깥으로 이동하는 경우, 그리고 대각선 파이프가 가로쪽과 세로쪽 맵 바깥에 있는 경우를 continue문을 이용하여 넘겨줍니다.

또한 파이프의 종류를 i를 이용하여 i가 0일 때를 가로, 1일때 세로, 2일 때 대각선 파이프로 설정하고

문제에서 (1, 2)에서 가로 파이프의 끝 쪽이 있다는 조건을 적용하여 시작점을 정합니다.