1938번

1938번 - 통나무 옮기기

단순한 BFS로 풀려고 했는데, 생각해줘야 할 예외 사항이 많아서 경우의 수를 나누었다.

일단 처음에 입력받는 부분에서 통나무 B위치(bx,by,bd) 와 마지막 놓을 E의 위치를 (ex,ey,ed) 를 구해주었다.

이때 bx,by 는 통나무 중심의 좌표이고, bd 는 통나무가 놓인 방향을 나타냈다. bd 가 0 이면 세로, 1이면 가로 방향.

통나무 중심의 위치는 통나무가 가로이건 세로이건, for 문 두번을 돌때 2번째가 통나무가 중심인 것으로 찾았다. 또 중심값을 통해 통나무의 

방향도 알아낼 수 있었다.

그리고 BFS를 수행하는 함수를 보면, 구조체를 만들어서 통나무의 좌표와 방향을 갖는 구조체를 큐의 인자로 넣는다.

chek 배열 같은 경우는 3차원 배열을 설정하여 check[x][y][d] 는 x,y를 중심으로 갖고 방향이 d인 통나무가 지나갔는지 여부를 판단했다.

그리고 경우의 수가 U,D,L,R,T 다섯가지 이므로 for문을 통해서 다섯가지 경우의 수를 나누었다. 그리고 경우를 천천히 나누었다.

U 일때 통나무의 방향이 세로냐, 가로냐에 따라서 조건이 달라지게 된다.

--- U이고, 통나무는 가로일 때, 중심값을 움직일 수 있는지를 본다.

이때 중심값이 n*n 의 맵 범위를 넘어가면 안되고, 중심값을 움직였을 때 통나무가 지나간적이 없어야 한다 (조건 1).

통나무를 옮겼을 때 움직인 세칸에 1 이 하나라도 존재하면 안된다 (조건 2)

--- U 이고, 통나무는 세로일 때, 중심값을 움직일 수 있는지를 본다.

이때도 역시 중심값이 n*n 의 맵 범위를 넘어가면 안되고, 중심값을 움직였을 때 통나무가 지나간적이 없어야 한다 (조건 1).

통나무를 옮겼을 때 움직인 한 칸에 1 이 존재하면 안된다 (조건 2) 

이런식으로 비슷하게 L 과 R 에 해당하는 경우의 수를 해결할 수 있다.

그리고 이제 T 일때를 보면 T 일때는, 문제의 예처럼 주변의 6칸을 탐색하면 되지만, 귀찮아서 그냥 중심값을 포함한 9칸을 탐색했다. 탐색한 

후에 만약 1이 한칸이라도 존재한다면 돌릴 수 없으므로 can_turn 변수를 false 로 변경한다.

만약 1이 존재하지 않지만 돌렸을 때 n*n 맵의 범위를 넘어가는지 확인한다. 이때는 중심값을 기준으로 상하좌우만을 확인하였다.

이렇게 체크를 하고 만약 돌릴 수 있는 상황이라면, 중심값은 유지한채 방향만을 돌려주면 된다. 0이면 1로, 1이면 0으로 

이런식으로 BFS를 돌리면서 경우를 체크하다가 놓고자 하는 위치에 도달하면 ( 즉 놓고자하는 곳의 좌표와 통나무의 방향이 일치하면 ) 

while 문을 빠져나오면서 BFS를 종료하고, dist 배열에 있는 값을 통해서 정답을 구한다.

<정답 코드>

#include<iostream>
#include<queue>
using namespace std;
 
typedef struct state{
    int x;
    int y;
    int dir;
}state;
int n,bx,by,bd,ex,ey,ed;
char map[51][51];
int dist[51][51][2];
bool check[51][51][2];
int x_around[9]={-1,-1,-1,0,0,0,1,1,1};
int y_around[9]={-1,0,1,-1,0,1,-1,0,1};
 
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
 
void bfs()
{
    queue<state> q;
 
    // B의 가운데 값을 시작점으로 큐에 넣기
    state start={bx,by,bd};
    q.push(start);
    dist[bx][by][bd]=0;
    check[bx][by][bd]=true;
 
 
    while(!q.empty())
    {
        int x=q.front().x;
        int y=q.front().y;
        int dir=q.front().dir;
        q.pop();
 
        if(x==ex && y==ey && dir==ed)
            break;
 
        for(int d=0;d<5;d++)
        {
            // U 실행
            if(d==0)
            {
                // 가로일 경우
                if(dir==1)
                {
                    if(x-1>=0 && y>=0 && x-1<n && y<n && !check[x-1][y][dir])
                    {
                        if(map[x-1][y]!='1' && map[x-1][y-1]!='1'&&map[x-1][y+1]!='1')
                        {
                            state tmp={x-1,y,dir};
                            dist[x-1][y][dir]=dist[x][y][dir]+1;
                            check[x-1][y][dir]=true;
                            q.push(tmp);
                        }
                    }
                }
                // 세로일 경우
                else
                {
                    if(x-2>=0 && y>=0 && x-2<n && y<n && !check[x-1][y][dir])
                    {
                        if(map[x-2][y]!='1')
                        {
                            state tmp={x-1,y,dir};
                            dist[x-1][y][dir]=dist[x][y][dir]+1;
                            check[x-1][y][dir]=true;
                            q.push(tmp);
                        }
                    }
 
                }
            }
            // D 실행
            else if(d==1)
            {
                // 가로일 경우
                if(dir==1)
                {
                    if(x+1>=0 && y>=0 && x+1<n && y<n && !check[x+1][y][dir])
                    {
                        if(map[x+1][y]!='1' && map[x+1][y-1]!='1'&&map[x+1][y+1]!='1')
                        {
                            state tmp={x+1,y,dir};
                            dist[x+1][y][dir]=dist[x][y][dir]+1;
                            check[x+1][y][dir]=true;
                            q.push(tmp);
                        }
                    }
                }
                // 세로일 경우
                else
                {
                    if(x+2>=0 && y>=0 && x+2<n && y<n && !check[x+1][y][dir])
                    {
                        if(map[x+2][y]!='1')
                        {
                            state tmp={x+1,y,dir};
                            dist[x+1][y][dir]=dist[x][y][dir]+1;
                            check[x+1][y][dir]=true;
                            q.push(tmp);
                        }
                    }
 
                }
            }
            // L 실행
            else if(d==2)
            {
                // 세로일 경우
                if(dir==0)
                {
                    if(x>=0 && y-1>=0 && x<n && y-1<n && !check[x][y-1][dir])
                    {
                        if(map[x][y-1]!='1' && map[x-1][y-1]!='1'&&map[x+1][y-1]!='1')
                        {
                            state tmp={x,y-1,dir};
                            dist[x][y-1][dir]=dist[x][y][dir]+1;
                            check[x][y-1][dir]=true;
                            q.push(tmp);
                        }
                    }
                }
                // 가로일 경우
                else
                {
                    if(x>=0 && y-2>=0 && x<n && y-2<n && !check[x][y-1][dir])
                    {
                        if(map[x][y-2]!='1')
                        {
                            state tmp={x,y-1,dir};
                            dist[x][y-1][dir]=dist[x][y][dir]+1;
                            check[x][y-1][dir]=true;
                            q.push(tmp);
                        }
                    }
 
                }
            }
            // R 실행
            else if(d==3)
            {
                // 세로일 경우
                if(dir==0)
                {
                    if(x>=0 && y+1>=0 && x<n && y+1<n && !check[x][y+1][dir])
                    {
                        if(map[x][y+1]!='1' && map[x-1][y+1]!='1'&&map[x+1][y+1]!='1')
                        {
                            state tmp={x,y+1,dir};
                            dist[x][y+1][dir]=dist[x][y][dir]+1;
                            check[x][y+1][dir]=true;
                            q.push(tmp);
                        }
                    }
                }
                // 가로일 경우
                else
                {
                    if(x>=0 && y+2>=0 && x<n && y+2<n && !check[x][y+1][dir])
                    {
                        if(map[x][y+2]!='1')
                        {
                            state tmp={x,y+1,dir};
                            dist[x][y+1][dir]=dist[x][y][dir]+1;
                            check[x][y+1][dir]=true;
                            q.push(tmp);
                        }
                    }
 
                }
            }
            // T 실행
            else
            {
                bool can_turn=true;
 
                // 주변에 1이 있는지 확인
                for(int k=0;k<9;k++)
                {
                    int tx=x+x_around[k];
                    int ty=y+y_around[k];
                    if(map[tx][ty]=='1')
                    {
                        can_turn=false;
                        break;
                    }
                }
 
                // 주변이 범위가 넘는지 확인
                for(int k=0;k<4;k++)
                {
                    int tx=x+dx[k];
                    int ty=y+dy[k];
                    if(tx<0 || ty<0 || tx>=n || ty>=n)
                    {
                        can_turn=false;
                        break;
                    }
                }
 
                if(can_turn)
                {
                    int ndir=1-dir;            // 1이면 0, 0이면 1
                    if(x>=0 && y>=0 && x<n && y<n && !check[x][y][ndir])
                    {
                        state tmp={x,y,ndir};
                        dist[x][y][ndir]=dist[x][y][dir]+1;
                        check[x][y][ndir]=true;
                        q.push(tmp);
                    }
                }
            }
        }    
    }
 
 
    cout<<dist[ex][ey][ed]<<endl;
}
int main()
{
    //freopen("input.txt","r",stdin);
 
    int cnt1=0;
    int cnt2=0;
 
    // 입력 및 B의 가운데 지점의 좌표와 E의 가운데 지점 좌표 찾기
    // bd,ed 는 가로일경우 1
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>map[i][j];
            if(map[i][j]=='B')
            {
                if(cnt1==1)
                {
                    bx=i,by=j;
                    if(j-1>=0 && map[i][j-1]=='B')
                        bd=1;
                }
                cnt1++;
            }
 
            if(map[i][j]=='E')
            {
                if(cnt2==1)
                {
                    ex=i,ey=j;
                    if(j-1>=0 && map[i][j-1]=='E')
                        ed=1;
                }
                cnt2++;
            }
        }
    }
 
    // BFS 함수 실행
    bfs();
 
    return 0;
}