[백준 1938번] 통나무 옮기기

link : https://www.acmicpc.net/problem/1938

통나무 옮기기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2252	578	420	24.896%

문제

가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다. 다음 지형을 보자.

B 0 0 1 1
B 0 0 0 0
B 0 0 0 0
1 1 0 0 0
E E E 0 0

위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하는 문제를 생각해 보자. BBB와 EEE의 위치는 임의로 주어진다. 단 문제에서 통나무의 길이는 항상 3이며 B의 개수와 E의 개수는 같다. 통나무를 움직이는 방법은 아래와 같이 상하좌우(Up, Down, Left, Right)와 회전(Turn)이 있다.

코드	의미
U	통나무를 위로 한 칸 옮긴다.
D	통나무를 아래로 한 칸 옮긴다.
L	통나무를 왼쪽으로 한 칸 옮긴다.
R	통나무를 오른쪽으로 한 칸 옮긴다.
T	중심점을 중심으로 90도 회전시킨다.

예를 들면, 다음과 같다. (초기상태로부터의 이동)

초기상태	상(U)	하(D)	좌(L)	우(R)	회전(T)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 0 0 1 0 0

이와 같은 방식으로 이동시킬 때에 그 움직일 위치에 다른 나무, 즉 1이 없어야만 움직일 수 있다. 그리고 움직임은 위의 그림과 같이 한 번에 한 칸씩만 움직인다. 단 움직이는 통나무는 어떤 경우이든지 중간단계에서 한 행이나 한 열에만 놓일 수 있다. 예를 들면 아래 그림에서 a와 같은 단계는 불가능하다. 그리고 회전의 경우에서는 반드시 중심점을 중심으로 90도 회전을 해야 한다. (항상 통나무의 길이가 3이므로 중심점이 있음)

그리고 이런 회전(Turn)이 가능하기 위해서는 그 통나무를 둘러싸고 있는 3*3 정사각형의 구역에 단 한 그루의 나무도 없어야만 한다. 즉, 아래그림 b, d와 같이 ?로 표시된 지역에 다른 나무, 즉 1이 없어야만 회전시킬 수 있다. 따라서 c와 같은 경우에, 통나무는 왼쪽 아직 벌채되지 않은 나무 때문에 회전시킬 수 없다.

a	b	c	d
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B 0 0 0 0 B 0 0 0 0 B 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? ? ? 0 0 0 B B B 0 0 0 ? ? ? 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 B 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? B ? 0 0 0 ? B ? 0 0 0 ? B ? 0 0 0 0 0 0 0

문제는 통나무를 5개의 기본동작(U, D, L, R, T)만을 사용하여 처음위치(BBB)에서 최종위치(EEE)로 옮기는 프로그램을 작성하는 것이다. 단, 최소 횟수의 단위 동작을 사용해야 한다.

입력

첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.

출력

첫째 줄에 최소 동작 횟수를 출력한다. 이동이 불가능하면 0만을 출력한다.

예제 입력 1 

5
B0011
B0000
B0000
11000
EEE00

예제 출력 1 

9

뭐라고 해야할까... 엄청 귀찮은 문제이다. 통나무를 일어선거 누운거 둘 다 움직이는 기능도 만들어야 하고,

조건들도 충족시켜줘야하기 때문이다. BFS이기 때문에 설명을 할 것은 없다!

#include <iostream>
#include <queue>
#include <set>
 
using namespace std;
 
int N;
char field[50][50];
bool lie_visited[50][50] = { false , };
bool stand_visited[50][50] = { false, };
 
set <pair<pair<int, bool>, pair<int, int>>> temp1;
pair<pair<int, bool>, pair<int, int>> temp2;
 
bool B_state; //true : 누운거, false : 일어선거
bool E_state;
bool B_first, E_first;
int B[2];
int E[2];
 
bool lie_up_inspect(int i, int j);
bool lie_down_inspect(int i, int j);
bool lie_left_inspect(int i, int j);
bool lie_right_inspect(int i, int j);
bool lie_transform_inspect(int i, int j);
 
bool stand_up_inspect(int i, int j);
bool stand_down_inspect(int i, int j);
bool stand_left_inspect(int i, int j);
bool stand_right_inspect(int i, int j);
bool stand_transform_inspect(int i, int j);
 
int main() {
 
    int temp_count = 0, temp_x, temp_y;
    bool temp_bool;
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
 
            cin >> field[i][j];
 
            if (field[i][j] == 'B' && B_first == false) {
                B[0] = i;
                B[1] = j;
                B_first = true;
            }
            else if (field[i][j] == 'E' && E_first == false) {
                E[0] = i;
                E[1] = j;
                E_first = true;
            }
        }
    }
 
    if (field[B[0]][B[1] + 1] == 'B') {
        B_state = true;
        B[0] = B[0];
        B[1] = B[1] + 1;
    }
    else {
        B_state = false;
        B[0] = B[0] + 1;
        B[1] = B[1];
    }
 
    if (field[E[0]][E[1] + 1] == 'E') {
        E_state = true;
        E[0] = E[0];
        E[1] = E[1] + 1;
    }
    else {
        E_state = false;
        E[0] = E[0] + 1;
        E[1] = E[1];
    }
 
    if (B_state == true) {
        lie_visited[B[0]][B[1]] = true;
    }
    else {
        stand_visited[B[0]][B[1]] = true;
    }
 
    temp1.insert(make_pair(make_pair(0, B_state), make_pair(B[0], B[1])));
 
    while (1) {
 
        if (temp1.empty() == true) {
            printf("0");
            break;
        }
 
        temp2 = *temp1.begin();
        temp_count = temp2.first.first;
        temp_bool = temp2.first.second;
        temp_x = temp2.second.first;
        temp_y = temp2.second.second;
 
        if (temp_x == E[0] && temp_y == E[1]) {
            printf("%d", temp_count);
            break;
        }
 
        switch (temp_bool) {
        case true:
            if (lie_up_inspect(temp_x, temp_y) == true && lie_visited[temp_x - 1][temp_y] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x - 1, temp_y)));
                lie_visited[temp_x - 1][temp_y] = true;
            }
            if (lie_down_inspect(temp_x, temp_y) == true && lie_visited[temp_x + 1][temp_y] == false) { 
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x + 1, temp_y))); 
                lie_visited[temp_x + 1][temp_y] = true;
            }            
            if (lie_left_inspect(temp_x, temp_y) == true && lie_visited[temp_x][temp_y - 1] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x, temp_y - 1)));
                lie_visited[temp_x][temp_y - 1] = true;
            }
            if (lie_right_inspect(temp_x, temp_y) == true && lie_visited[temp_x][temp_y + 1] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x, temp_y + 1)));
                lie_visited[temp_x][temp_y + 1] = true;
            }
            if (lie_transform_inspect(temp_x, temp_y) == true && stand_visited[temp_x][temp_y] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, false), make_pair(temp_x, temp_y)));
                stand_visited[temp_x][temp_y] = true;
            }
            break;
 
        case false:
            if (stand_up_inspect(temp_x, temp_y) == true && stand_visited[temp_x - 1][temp_y] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x - 1, temp_y)));
                stand_visited[temp_x - 1][temp_y] = true;
            }
            if (stand_down_inspect(temp_x, temp_y) == true && stand_visited[temp_x + 1][temp_y] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x + 1, temp_y)));
                stand_visited[temp_x + 1][temp_y] = true;
            }
            if (stand_left_inspect(temp_x, temp_y) == true && stand_visited[temp_x][temp_y - 1] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x, temp_y - 1)));
                stand_visited[temp_x][temp_y - 1] = true;
            }
            if (stand_right_inspect(temp_x, temp_y) == true && stand_visited[temp_x][temp_y + 1] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, temp_bool), make_pair(temp_x, temp_y + 1)));
                stand_visited[temp_x][temp_y + 1] = true;
            }
            if (stand_transform_inspect(temp_x, temp_y) == true && lie_visited[temp_x][temp_y] == false) {
                temp1.insert(make_pair(make_pair(temp_count + 1, true), make_pair(temp_x, temp_y)));
                lie_visited[temp_x][temp_y] = true;
            }
            break;
        }
 
        temp1.erase(temp1.begin());
    }
 
 
    return 0;
}
 
bool lie_up_inspect(int i, int j) {
    if (i != 0 && field[i - 1][j - 1] != '1' && field[i - 1][j] != '1' && field[i - 1][j + 1] != '1') return true;
    else return false;
}
bool lie_down_inspect(int i, int j) {
    if (i != N - 1 && field[i + 1][j - 1] != '1' && field[i + 1][j] != '1' && field[i + 1][j + 1] != '1') return true;
    else return false;
}
bool lie_left_inspect(int i, int j) {
    if (j - 1 != 0 && field[i][j - 2] != '1') return true;
    else return false;
}
bool lie_right_inspect(int i, int j) {
    if (j + 1 != N - 1 && field[i][j + 2] != '1') return true;
    else return false;
}
bool lie_transform_inspect(int i, int j) {
    if (lie_up_inspect(i, j) == true && lie_down_inspect(i, j) == true) return true;
    else return false;
}
 
bool stand_up_inspect(int i, int j) {
    if (i - 1 != 0 && field[i - 2][j] != '1') return true;
    else return false;
}
bool stand_down_inspect(int i, int j) {
    if (i + 1 != N - 1 && field[i + 2][j] != '1') return true;
    else return false;
}
bool stand_left_inspect(int i, int j) {
    if (j != 0 && field[i - 1][j - 1] != '1' && field[i][j - 1] != '1' && field[i + 1][j - 1] != '1') return true;
    else return false;
}
bool stand_right_inspect(int i, int j) {
    if (j != N - 1 && field[i - 1][j + 1] != '1' && field[i][j + 1] != '1' && field[i + 1][j + 1] != '1') return true;
    else return false;
}
bool stand_transform_inspect(int i, int j) {
    if (stand_left_inspect(i, j) == true && stand_right_inspect(i, j) == true) return true;
    else return false;
}