[BOJ 17070] 파이프 옮기기 (C++)

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

17070번: 파이프 옮기기 1

 

#include <bits/stdc++.h>

using namespace std;
enum Pos {garo, sero, degak};
int house[17][17];

class Point{
    public:
        int y;
        int x;
        Pos pos;
        Point(int y, int x, Pos pos){
            this->y=y;
            this->x=x;
            this->pos=pos;
        } 
};

bool isPossible(int y, int x){
    if (house[y+1][x]==0 && house[y][x+1]==0 && house[y+1][x+1]==0){
        return true;
    }
    else{
        return false;
    }
}
int main(){
    int N, x;
    cin>>N;
    int visited[3][N+1][N+1];
    memset(visited, 0, sizeof(int)*3*(N+1)*(N+1));
    int cnt=0;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=N; j++){
            cin>>x;
            house[i][j]=x;
        }
    }
    queue<Point *> q;
    q.push(new Point(1,2,garo));
    //visited[garo][1][2]=1;
    while (!q.empty()){
        Point *p=q.front();
        q.pop();
        if (p->y==N && p->x==N){
            cnt++;
            //visited[p->pos][p->y][p->x]=0;
            continue;
        }
        int nx=(p->x)+1;    
        int ny=(p->y)+1;    
        if (p->pos==garo){      
            if (nx>=1 && nx<=N){
                if (house[p->y][nx]==0){
                    //visited[garo][p->y][nx]=1;
                    q.push(new Point(p->y, nx, garo));
                }
            }
            if (ny>=1 && ny<=N && nx>=1 && nx<=N){
                if (isPossible(p->y, p->x)){
                    //visited[degak][ny][nx]=1;
                    q.push(new Point(ny, nx, degak));
                }
            }
        }
        else if (p->pos==sero){
            if (ny>=1 && ny<=N){
                if (house[ny][p->x]==0){
                    //visited[sero][ny][p->x]=1;
                    q.push(new Point(ny,p->x,sero));
                }
            }
            if (ny>=1 && ny<=N && nx>=1 && nx<=N){
                if (isPossible(p->y, p->x)){
                    //visited[degak][ny][nx]=1;
                    q.push(new Point(ny, nx, degak));
                }
            }
        }
        else{
            if (nx>=1 && nx<=N){
                if (house[p->y][nx]==0){
                    //visited[garo][p->y][nx]=1;
                    q.push(new Point(p->y, nx, garo));
                }
            }
            if (ny>=1 && ny<=N){
                if (house[ny][p->x]==0){
                    //visited[sero][ny][p->x]=1;
                    q.push(new Point(ny,p->x,sero));
                }
            }
            if (ny>=1 && ny<=N && nx>=1 && nx<=N){
                if (isPossible(p->y, p->x)){
                    //visited[degak][ny][nx]=1;
                    q.push(new Point(ny, nx, degak));
                }
            }
        }
    }
    cout<<cnt<<"\n";
    return 0;
}

 

BFS 로 탐색하는 문제.

그러나 다른점은 visited 배열을 사용할 필요 없다는거! (너무 정형화된 생각을 하는 바람에 visited 배열을 만들어서 괜히 헤맴)

어차피 이동 방향이 무한 루프를 돌 수 없는 구조로 설정되어있다.

그리고 최단 거리를 구하는게 아니라 (N, N) 까지 도달하는 가짓수를 구하는 것임에 유의하기.

 

코드를 간결하게 짜지 못한거 같다.

다른 분의 코드를 보니 (출처: https://binux.tistory.com/36 ) 탐색할 수 있는 위치인지 파악하는 함수를 따로 만들고(벽인지 체크, 경계를 벗어나는지 체크, direction에 따라 벽을 체크한다), 이동하는 함수를 따로 만들면 간결해짐을 알 수 있었다. 

이동 방향을 주고 현 가로방향이면 move(세로방향), move(대각선방향) 이런 식으로.

가능한지 체크하고->가능하면 큐에 이동방향에 맞게 넣어주고->(n,n) 일때 카운팅해주면 된다.