[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int shape;
}node;
 
char map[55][55];
int visited[55][55][2]; // 가로모양, 세로모양 
int N;
bool Move = false;
 
int first_B_x, first_B_y;
int first_E_x, first_E_y;
int mid_B_x, mid_B_y;
int mid_E_x, mid_E_y;
int B_shape;
int E_shape;
 
queue<node> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int check(int x, int y)
{
    for(int i = x-1; i <= x+1; i++)
    {
        for(int j = y-1; j <= y+1; j++)
        {
            if(safe(i, j) == 0)
            {
                return 0;
            }
            else if(safe(i, j) == 1)
            {
                if(map[i][j] == '1')
                {
                    return 0;
                }
            }
        }
    }
    
    return 1;
}
 
void BFS(int x, int y, int shape)
{
    visited[x][y][shape] = 1;
    q.push({x, y, shape});
    
    while(!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        shape = q.front().shape;
        q.pop();
        
        if(x == mid_E_x && y == mid_E_y && shape == E_shape)
        {
            Move = true;
            return;
        }
        
        // 상하좌우 
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos][shape] == 0 && map[xpos][ypos] != '1')
            {
                // 가로 
                if(shape == 0)
                {
                    if(safe(xpos, ypos-1) == 1 && safe(xpos, ypos+1) == 1 && map[xpos][ypos-1] != '1' && map[xpos][ypos+1] != '1')
                    {
                        visited[xpos][ypos][shape] = visited[x][y][shape]+1;
                        q.push({xpos, ypos, shape});
                    }
                }
                // 세로 
                else if(shape == 1)
                {
                    if(safe(xpos-1, ypos) == 1 && safe(xpos+1, ypos) == 1 && map[xpos-1][ypos] != '1' && map[xpos+1][ypos] != '1')
                    {
                        visited[xpos][ypos][shape] = visited[x][y][shape]+1;
                        q.push({xpos, ypos, shape});
                    }
                }
            }
        }
        
        // 회전 
        if(check(x, y) == 1)
        {
            // 가로 -> 세로 
            if(shape == 0)
            {
                if(visited[x][y][1] == 0)
                {
                    visited[x][y][1] = visited[x][y][0]+1;
                    q.push({x, y, 1});
                }
            }
            // 세로 -> 가로 
            else if(shape == 1)
            {
                if(visited[x][y][0] == 0)
                {
                    visited[x][y][0] = visited[x][y][1]+1;
                    q.push({x, y, 0});
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1938_input.txt", "r", stdin);
 
    cin >> N;
    
    int find_mid_B = 1;
    int find_mid_E = 1;
    
    for(int i = 0; i < N; i++)
    {
        string input;
        cin >> input;
        
        for(int j = 0; j < N; j++)
        {
            map[i][j] = input[j];
            
            if(map[i][j] == 'B' && find_mid_B == 1)
            {
                first_B_x = i;
                first_B_y = j;
                
                find_mid_B++;
            }
            else if(map[i][j] == 'B' && find_mid_B == 2)
            {
                mid_B_x = i;
                mid_B_y = j;
                
                find_mid_B++;
            }
            
            if(map[i][j] == 'E' && find_mid_E == 1)
            {
                first_E_x = i;
                first_E_y = j;
                
                find_mid_E++;
            }
            else if(map[i][j] == 'E' && find_mid_E == 2)
            {
                mid_E_x = i;
                mid_E_y = j;
                
                find_mid_E++;
            }
        }
    }
    
    // 출발 통나무 - 가로 
    if(first_B_x - mid_B_x == 0)
    {
        B_shape = 0;
    }
    // 출발 통나무 - 세로 
    else if(first_B_x - mid_B_x == -1)
    {
        B_shape = 1;
    }
    
    // 도착 통나무 - 가로 
    if(first_E_x - mid_E_x == 0)
    {
        E_shape = 0;
    }
    // 도착 통나무 - 세로 
    else if(first_E_x - mid_E_x == -1)
    {
        E_shape = 1;
    }
    
    BFS(mid_B_x, mid_B_y, B_shape);
    
    if(Move == false)
    {
        cout << "0";
    }
    else
    {
        cout << visited[mid_E_x][mid_E_y][E_shape]-1;
    }
           
    return 0; 
}