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

문제는 다음과 같다.

오늘은 백준1938번 통나무 옮기기 문제를 풀어보도록 하자.

풀다가 통나무에 깔려 죽을뻔했다. 큐 관리는 간단했으나 구현부분이 너무 까다로웠기 때문이다.

우선 처음 통나무,목적지의 좌표와 모양을 체크했다. 통나무 중심점의 좌표와 모양 (가로:0, 세로:1)을 큐에 넣어주고 목적지의 좌표와 모양을 변수에 저장해주었다.

그리고 visit배열을 3차원으로 해주었는데 그 이유는 좌표값과 모양을 체크해줘야 하기 때문이다. 만일 visit[0][2][1]이면 y=2, x=1 , 가로모양이라는 뜻이고

visit[1][2][1]이면 y=2, x=1, 세로모양이라는 뜻이 된다. 즉, 좌표 중복을 체크하되 모양까지 체크해줘야 하는 것이다.

그 후 BFS를 큐 사이즈마다 돌려주었다. 왜냐하면 최솟값을 찾는 것이기 때문에 큐의 턴 관리를 해주어야 한다. 즉, 상하좌우턴 5번을 하고 answer++;를 하며

한 번 움직였다고 체크를 해주는게 아니라 들어있는 모든 큐를 각각 상하좌우턴 5번을 하고 answer++;를 해주어야 한다.

그리고 move함수를 통하여 상하좌우를 구현하였고 턴은 중심점이 바뀌지 않고 모양만 바뀌므로 따로 구현해주었다.

                                     [코드]
#include <iostream>
#include <queue>
using namespace std;

char map[50][50];
bool visit[2][50][50];//up,down,left,right,turn
int dir[8][2] = { {-1,0},{0,1},{1,0},{0,-1},{-1,-1},{-1,1},{1,1},{1,-1} };
//북,동,남,서,북서,북동,남동,남서
int N, answer = 0, answer_y, answer_x, answer_shape;
struct pos {
	int y;
	int x;
	int shape;//0 : 가로, 1 : 세로
};
queue<pos>Q, answer_Q;

bool Inbound(int y, int x) {
	return y >= 0 && x >= 0 && y < N && x < N;
}

void check_shape() {
	int y = Q.front().y;
	int x = Q.front().x;
	int shape = Q.front().shape;

	Q.pop();

	if (y + 1 == Q.front().y) {//세로
		y = Q.front().y;
		x = Q.front().x;
		shape = 1;
		Q.push({ y,x,shape });
		visit[1][y][x] = true;
	}
	else {//가로
		y = Q.front().y;
		x = Q.front().x;
		shape = 0;
		Q.push({ y,x,shape });
		visit[0][y][x] = true;
	}
	Q.pop(); Q.pop();

	y = answer_Q.front().y;
	x = answer_Q.front().x;
	shape = answer_Q.front().shape;

	answer_Q.pop();

	if (y + 1 == answer_Q.front().y) {//세로
		answer_y = answer_Q.front().y;
		answer_x = answer_Q.front().x;
		answer_shape = 1;
	}
	else {//가로
		answer_y = answer_Q.front().y;
		answer_x = answer_Q.front().x;
		answer_shape = 0;
	}
}

bool move(int y, int x, int shape, int i) {
	if (shape == 1) {//세로
		if (!visit[shape][y][x]) {
			if (i == 0) {//상
				y += dir[i][0];

				if (Inbound(y, x)) {
					if (map[y][x] != '1') {
						return true;
					}
				}
			}
			else if (i == 1 || i == 3) {//우, 좌
				int y_1 = y + dir[0][0];
				int y_2 = y + dir[2][0];

				if (map[y_1][x] != '1' && map[y][x] != '1' && map[y_2][x] != '1') {
					return true;
				}
			}
			else {//하
				y += dir[i][0];

				if (Inbound(y, x) && map[y][x] != '1') {
					return true;
				}
			}
		}
	}
	else {//가로
		if (!visit[shape][y][x]) {
			if (i == 0 || i == 2) {//상,하
				int x_1 = x + dir[1][1];
				int x_2 = x + dir[3][1];

				if (map[y][x_1] != '1' && map[y][x] != '1' && map[y][x_2] != '1') {
					return true;
				}
			}
			else if (i == 1) {//우
				x += dir[i][1];

				if (Inbound(y, x)) {
					if (map[y][x] != '1') {
						return true;
					}
				}
			}
			else {//좌
				x += dir[i][1];

				if (Inbound(y, x)) {
					if (map[y][x] != '1') {
						return true;
					}
				}
			}
		}
	}
	return false;
}

bool bfs() {
	while (!Q.empty()) {
		answer++;
		int size_of_Q = Q.size();

		for (int m = 0; m < size_of_Q; m++) {
			int y = Q.front().y;
			int x = Q.front().x;
			int shape = Q.front().shape;

			Q.pop();

			for (int i = 0; i < 4; i++) { //상,우,하,좌
				int my = y + dir[i][0];
				int mx = x + dir[i][1];

				if (!Inbound(my, mx) || map[my][mx] == '1') continue;

				if (move(my, mx, shape, i)) {
					if (my == answer_y && mx == answer_x && shape == answer_shape) {
						return true;
					}
					Q.push({ my,mx,shape });
					visit[shape][my][mx] = true;
				}
			}
			int cnt = 0;
			for (int i = 0; i < 8; i++) {//턴
				int t_y = y + dir[i][0];
				int t_x = x + dir[i][1];

				if (Inbound(t_y, t_x)) {
					if (map[t_y][t_x] != '1') {
						cnt++;
					}
				}
			}
			if (cnt == 8) {
				if (shape == 1) {
					if (!visit[0][y][x]) {
						Q.push({ y,x,0 });
						visit[0][y][x] = true;
					}
				}
				else {
					if (!visit[1][y][x]) {
						Q.push({ y,x,1 });
						visit[1][y][x] = true;
					}
				}
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	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') {
				Q.push({ i,j,-1 });
			}
			if (map[i][j] == 'E') {
				answer_Q.push({ i,j,-1 });
			}
		}
	}
	check_shape();//처음 위치 파악
	if (bfs()) {
		cout << answer;
	}
	else {
		cout << 0;
	}
}