백준 17070번 치킨배달 C++ 풀이

백준 17070번 치킨배달 C++ 풀이

문제 설명

크기가 NxN 격자판이 주어지며 칸의크기는 1x1이다. 파이프를 밀어서 옮기려고 하는데

이 때 파이프는 가로,세로, 대각선으로 이동을 할 수 있는데 이동할 때는 항상 빈칸일 때만 이동이 가능하다.

파이프가 가로 방향일 때는 가로와 대각선, 세로 방향일 때는 세로와 대각선, 대각선 방향일 때는 가로,세로 대각선 방향 모두 이동이 가능하다.

가장 처음에 파이프는 (1,1)와 (1,2)를 차지하고 있고, 방향은 가로이다.

이 때 (N,N)으로 이동 시키는 방법의 개수를 구해야 한다.

풀이

우선 이문제를 보았을 때 방향에 따라 이동할 수 있는 곳이 달라지므로 dir이라는 변수를 두어서 해당 변수 값에 따라 이동 할 곳을 결정하였다.

습관적으로 BFS,DFS를 풀 때 방문한 곳을 확인하여 해당 코드도 구현을 하였는데 파이프가 이동하는 방향이 3부분으로 정해져 이동하기 때문에 굳이 필요 없다는 것을 다 구현하고 실행 테스트 하면서 깨달았다.

1. 이동 방향은 대각선: 0, 가로: 1, 세로: 2로 정하였다.
2. 가로일 때 세로 방향을 제외, 세로일 때 가로 방향을 제외 하였다.
3. 특히 대각선일 때 이동할 때 걸리는 3칸 모두 비어 있어야 한다.(고생 Point)

위의 방법으로 BFS,DFS 두 개의 방법으로 모두 구현해 보았다.

int dx[] = {1,0,1};
int dy[] = {1,1,0};

void dfs(int curX,int curY,int dir){
    if(curX == n-1 && curY == n-1){
        answer++;
        return;
    }

    for(int i = 0; i < 3; i++){
        if(dir == 1 && i ==  2) continue;
        if(dir == 2 && i ==  1) continue;

        int nextX = curX + dx[i];
        int nextY = curY + dy[i];

        if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
        if(map[nextX][nextY] == 1) continue;
        if(i == 0 && (map[curX][nextY] == 1 || map[nextX][curY] == 1)) continue;
        
        dfs(nextX,nextY,i);
    }
}

queue<pair<pair<int,int>,int>> q;

void bfs(){

    while(!q.empty()){
        int curX = q.front().first.first;
        int curY = q.front().first.second;
        int dir = q.front().second;
        q.pop();

        if(curX == n-1 && curY == n-1){
            answer++;
        }

        for(int i = 0; i < 3; i++){
            if(dir == 1 && i ==  2) continue;
            if(dir == 2 && i ==  1) continue;

            int nextX = curX + dx[i];
            int nextY = curY + dy[i];

            if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
            if(map[nextX][nextY] == 1) continue;
            if(i == 0 && (map[curX][nextY] == 1 || map[nextX][curY] == 1)) continue;

            q.push({{nextX,nextY},i});
        }
    }
}

C++ 전체 소스코드