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

백준의 통나무 옮기기(1938) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 문제가 딱 봐도 너무 복잡해보인다. 문제를 읽어보면 그리 어렵지는 않은데, 뭔가 복잡해보이긴 한다. 문제를 다시 한번

   정리해보고 문제를 구현하는 큰 틀에 대해서 알아보자.

   3칸짜리 통나무가 하나 있다. 통나무는 가로로 누워서 1x3 모양의 통나무로 존재할 수도 있고, 세로로 서있는 3x1모양의

   통나무로 존재할 수도 있다. 이 때, B로 표현된 통나무 위치에서, E로 표현된 위치까지 가기 위해서는 몇번 움직여야

   하는지 구해야 하는 문제이다.

   그렇다면, 어떻게 구현해야 할지 단계별로 알아보고, 단계별로 구체적으로 어떻게 해야하는지 까지 알아보자.

   ( 지금부터 편의상 통나무가 세로로 놓여져있는 형태를 서있는 형태, 가로로 놓여져 있는 형태를 누워있는 형태라 하겠다 )

   1. 통나무의 초기 위치와 서있는 형태, 통나무가 도착해야 하는 곳에서의 통나무의 형태를 파악하자.

   → 제일 처음 통나무가 서있는 형태인지 누워있는 형태인지를 파악해야 한다. 통나무의 형태에 따라서 계산할 수 있는

      움직임이 달라지기 때문에 형태를 파악하는 것이 중요하다.

   → 본인은, 통나무가 누워있는 형태를 0으로, 서있는 형태를 1로 관리하였다. 그렇다면, 초기에 통나무의 형태를

      어떻게 구할지 알아보자. 본인은 처음 입력받을 때, 'B'로 입력되는 값 3개와, 'E'로 입력되는 값 3개의 좌표를

      저장해주었다.

     

      예를 들어서, 왼쪽이 맵에서 입력으로 주어진 B와 E의 상태라면, 오른쪽의 표처럼 값으로 저장해주었다.

      각각의 Index에는 x좌표값과 y좌표값을 저장하도록 pair로 관리해주었다.

      아 그리고, 본인은 통나무가 누워있는 모양을 0으로 표현, 통나무가 서 있는 모양을 1로 표현해주었다.

      즉, Start[0].x좌표 == Start[1].x좌표 == Start[2].x좌표 라면 누워있는 모양, 즉 0의 값을 갖도록 해주었고, 그게 아니

      라면 1의 값을 갖도록 설정해 주었다.

      본문함수 = int Check_Shape(pair<int,int> S[3])

     

    2. 통나무를 전체를 관리하지 말고, 가운데 중심점만 가지고 통나무를 관리하자.

    → 통나무를 굳이 3개의 점을 모두 가지고 다닐 필요는 없다. 중심점 하나만으로도 통나무를 관리할 수 있다.

      주의해야 할 점은, 같은 점에 2개의 모양이 올 수 있다는 점이다. 이 문제에서도 분명히 이미 탐색한 좌표는 더 이상

      탐색하지 않는 중복을 방지해주는 배열을 사용할 것이다. 이 때, 3차원 배열을 사용해서 2개의 모양까지는 올 수 있도록

      신경써주자.

     

      위의 말대로 중심점만 관리한다면, 위의 그림처럼 (1, 1)에 중심점이 있다고 가정해보자. 하지만, (1, 1)에서는 2개의

      모양이 가능하다. 빨강색처럼 누워있는 모양, 파랑색처럼 서있는 모양, 총 2개가 가능하므로

      Visit[][] 배열을 2차원이 아닌 Viist[][][] 3차원으로 관리해서, Visit[x좌표][y좌표][통나무의형태] 로 관리해주자 !

    3. 누워있을 때와 서있을 때의 구현을 따로 해줘야 한다.

    → 누워있을 경우에 통나무를 상하좌우 혹은 돌리는 것과, 서있는 경우에 통나무를 상하좌우 혹은 돌리는 것에 대한

       구현 내용이 달라진다. 신경을 써야 하는 좌표의 범위와 맵의 상태도 달라지기 때문에 따로 구현해주는 것이 좋다.

 

   실제로 통나무를 옮기고, 회전시키는 과정은 소스코드로 대체하겠다. 실제로 옮기는 부분은 범위만 잘 생각하고, 언제

   통나무가 움직일 수 있는지만 잘 생각한다면 어렵지 않기 때문이다. 단지 약간 복잡할 뿐 !

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, B_Shape, E_Shape;
char MAP[MAX][MAX];
bool Visit[MAX][MAX][2];
 
pair<int, int> Start[3], End[3], B_Center, E_Center;
 
int C_dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int C_dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
void Input()
{
    cin >> N;
    int S_Idx = 0;
    int E_Idx = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'B')
            {
                Start[S_Idx].first = i;
                Start[S_Idx].second = j;
                S_Idx++;
 
                MAP[i][j] = '0';
            }
            else if (MAP[i][j] == 'E')
            {
                End[E_Idx].first = i;
                End[E_Idx].second = j;
                E_Idx++;
 
                MAP[i][j] = '0';
            }
        }
    }
    B_Center.first = Start[1].first;
    B_Center.second = Start[1].second;
    E_Center.first = End[1].first;
    E_Center.second = End[1].second;
}
 
int Check_Shape(pair<int, int> S[3])
{
    if (S[0].first == S[1].first && S[1].first == S[2].first) return 0;
    else return 1;
}
 
bool Change_Shape(int x, int y, int Shape)
{
    if (Shape == 0)
    {
        for (int i = 0; i < 8; i++)
        {
            if (i == 3 || i == 4) continue;
 
            int nx = x + C_dx[i];
            int ny = y + C_dy[i];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
            if (MAP[nx][ny] == '1') return false;
        }
    }
    else if (Shape == 1)
    {
        for (int i = 0; i < 8; i++)
        {
            if (i == 1 || i == 6) continue;
 
            int nx = x + C_dx[i];
            int ny = y + C_dy[i];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
            if (MAP[nx][ny] == '1') return false;
        }
    }
    return true;
}
 
int BFS(int a, int b)
{
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(a, b), make_pair(B_Shape, 0)));
    Visit[a][b][B_Shape] = true;
 
    while (Q.empty() == 0)
    {
        bool F = false;
 
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int S = Q.front().second.first;
        int Cnt = Q.front().second.second;
        Q.pop();
 
        if (x == E_Center.first && y == E_Center.second && S == E_Shape)
        {
            return Cnt;
        }
 
        if (S == 0) // ㅡ 이렇게 누워있는 모양이라면
        {
            int nx = x - 1;
            int ny = y;
            // Up
            if (nx >= 0 && ny - 1 >= 0 && ny + 1 < N && Visit[nx][ny][S] == false)
            {
                if (MAP[nx][ny] == '0' && MAP[nx][ny - 1] == '0' && MAP[nx][ny + 1] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            nx = x + 1;
            ny = y;
            // Down
            if (nx < N && ny - 1 >= 0 && ny + 1 < N && Visit[nx][ny][S] == false)
            {
                if (MAP[nx][ny] == '0' && MAP[nx][ny - 1] == '0' && MAP[nx][ny + 1] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            nx = x;
            ny = y - 1;
            int nny = y - 2;
            // Left
            if (nny >= 0 && Visit[nx][ny][S] == false)
            {
                if (MAP[nx][nny] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            nx = x;
            ny = y + 1;
            nny = y + 2;
            // Right
            if (nny < N && Visit[nx][ny][S] == false)
            {
                if (MAP[nx][nny] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            // Turn
            if (Change_Shape(x, y, S) == true && Visit[x][y][1] == false)
            {
                Visit[x][y][1] = true;
                Q.push(make_pair(make_pair(x, y), make_pair(1, Cnt + 1)));
            }
        }
        else    // 1 이렇게 서있는 모양
        {
            int nx = x - 1;
            int ny = y;
            int nnx = x - 2;
            // Up
            if (nnx >= 0 && Visit[nx][ny][S] == false)
            {
                if (MAP[nnx][ny] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            nx = x + 1;
            ny = y;
            nnx = x + 2;
            // Down
            if (nnx < N && Visit[nx][ny][S] == false)
            {
                if (MAP[nnx][ny] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            nx = x;
            ny = y - 1;
            // Left
            if (ny >= 0 && nx - 1 >= 0 && nx + 1 < N && Visit[nx][ny][S] == false)
            {
                if (MAP[nx][ny] == '0' && MAP[nx - 1][ny] == '0' && MAP[nx + 1][ny] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            nx = x;
            ny = y + 1;
            // Right
            if (ny < N && nx - 1 >= 0 && nx + 1 < N && Visit[nx][ny][S] == false)
            {
                if (MAP[nx][ny] == '0' && MAP[nx - 1][ny] == '0' && MAP[nx + 1][ny] == '0')
                {
                    Visit[nx][ny][S] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(S, Cnt + 1)));
                }
            }
 
            // Turn
            if (Change_Shape(x, y, S) == true && Visit[x][y][0] == false)
            {
                Visit[x][y][0] = true;
                Q.push(make_pair(make_pair(x, y), make_pair(0, Cnt + 1)));
            }
        }
    }
    return 0;
}
 
void Solution()
{
    B_Shape = Check_Shape(Start);
    E_Shape = Check_Shape(End);
    
    cout << B_Shape << " , " << E_Shape << endl;
    int R = BFS(B_Center.first, B_Center.second);
    cout << R << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}