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

[문제]

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

[풀이]

처음에 파이프는 가로 방향을  (1,1)과 (1,2)에 위치한다.

파이프는 회전을 할 수 있으며

파이프가 이동하여 (N,N)에 도달할 수 있는 방법의 수를 출력하면 된다. 

 

BFS 방법으로 풀어보고 DFS 방법으로도 풀어봤다.

 

- BFS

visited 배열을 사용해 좌표와 현재 방향과 앞으로 나아갈 방향을 가지고 방문한 곳은 1로 update 해주었다.

이미 확인한 곳은 다시 방문하지 않도록 했는데 틀렸습니다가 나왔다. 아직도 이거는 왜 틀린지 모르겠다.

 

생각해보니 visited 배열이 굳이 필요하지 않을 것 같아서 없이 풀었더니 맞았습니다가 나왔다.

근데 시간이 너무 오래 걸린다.

 

 

- DFS

다음 좌표를 재귀로 호출해가며 (N,N)에 도달하면 끝나도록 했다.

 

 

[코드]

 

- DFS 방법

시간 : 116ms

 

#include <iostream>

#define MAX 17

using namespace std;
int map[MAX][MAX]={0,};
int N;

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

int cnt= 0;

void DFS(int x, int y, int dir)
{
    if(x == N-1 && y == N-1){
        cnt++;
        return;
    }
    for(int i=0;i<3;i++){
        
        if( dir == 0 && i==2)  continue;
        else if( dir == 2 && i==0)   continue;
        
        int nx =x+dx[i];
        int ny = y+dy[i];
        if(nx >= N || ny >= N ||map[nx][ny] == 1 ) continue;
        if(i==1 && (map[nx][ny-1] !=0 || map[nx-1][ny]!=0)) continue;
        
        DFS(nx,ny,i);
    }
}

int main(void)
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&map[i][j]);
        }
    }
    
    DFS(0,1,0);
    printf("%d",cnt);
    return 0;
}

 

 

- BFS 방법

시간 : 240ms

 

#include <iostream>
#include <queue>

#define MAX 17

using namespace std;

struct pos{
    int x,y,dir;
};

int map[MAX][MAX]={0,};
int N;

int dx[3] = {0,1,1};
int dy[3] = {1,1,0};
// dir : 가로 0, 대각석 1, 세로 2

void BFS()
{
    int cnt =0;
    int visited[MAX][MAX][3][3]={0,};

    queue <pos> q;
    
    q.push({0,1,0});
    
    while(!q.empty())
    {
        int x= q.front().x;
        int y= q.front().y;
        int dir = q.front().dir;
        if( x== N-1 && y == N-1)    cnt++;
        q.pop();
        
        for(int i=0;i<3;i++){
            
            if(dir ==0 && i==2) continue;
            else if(dir == 2 && i ==0)  continue;
            
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= N ) continue;
            if(map[nx][ny] == 1)    continue;
            if(i==1 && (map[nx][ny-1] !=0 || map[nx-1][ny]!=0)) continue;
            
            q.push({nx,ny,i});
        }
    }
    printf("%d",cnt);
    return ;
}

int main(void)
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&map[i][j]);
        }
    }
    
    BFS();
    return 0;
}