[C++] 프로그래머스 2020 KAKAO BLIND RECRUITMENT 블록 이동하기

(4시간)

단순한 BFS로 미로 찾기 문제에 조건들이 추가된 느낌.

머리 속에 생각한 방법을 그대로 코드로 구현하니 돌아갔다ㅋㅋ

다차원 배열으로 방문 체크도 써봤다.

근데 구현하고 보니 시간이 너무 오래 지나가 있는 문제...

#include <string>
#include <vector>
#include <queue>

using namespace std;

int N;
int visited[100][100][100][100];
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
vector<vector<int>> boards;

struct robot {
	int x1;
	int y1;
	int x2;
	int y2;
	int direction;
	int count;

	robot(int _x1, int _y1, int _x2, int _y2, int _direction, int _count) {
		x1 = _x1;
		y1 = _y1;
		x2 = _x2;
		y2 = _y2;
		direction = _direction;
		count = _count;
	}
};

bool checkMove(robot bot) {
	if (bot.x1 < 0 || bot.y1 < 0 || bot.x2 < 0 || bot.y2 < 0) return false;
	if (bot.x1 >= N || bot.y1 >= N || bot.x2 >= N || bot.y2 >= N) return false;
	if (boards[bot.x1][bot.y1] == 1 || boards[bot.x2][bot.y2] == 1) return false;
	if (visited[bot.x1][bot.y1][bot.x2][bot.y2] == 1) return false;
	if (visited[bot.x2][bot.y2][bot.x1][bot.y1] == 1) return false;
	return true;
}

bool checkRotate(int x1, int y1, int x2, int y2) {
	if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0) return false;
	if (x1 >= N || y1 >= N || x2 >= N || y2 >= N) return false;
	if (boards[x1][y1] == 1 || boards[x2][y2] == 1) return false;
	return true;
}

int solution(vector<vector<int>> board) {
	N = board.size();
	boards = board;

	queue<robot> q;

	robot start(0, 0, 0, 1, 0, 0);

	q.push(start);

	while (!q.empty()) {
		robot now = q.front();
		q.pop();

		// 목적지 도착
		if (now.x1 == N - 1 && now.y1 == N - 1) return now.count;
		if (now.x2 == N - 1 && now.y2 == N - 1) return now.count;

		visited[now.x1][now.y1][now.x2][now.y2] = 1;
		visited[now.x2][now.y2][now.x1][now.y1] = 1;

		// 상하좌우 움직이는 경우
		for (int i = 0; i < 4; i++) {
			robot next(now.x1 + dir[i][0], now.y1 + dir[i][1], now.x2 + dir[i][0], now.y2 + dir[i][1], now.direction, now.count + 1);
			if (checkMove(next)) {
				visited[next.x1][next.y1][next.x2][next.y2] = 1;
				visited[next.x2][next.y2][next.x1][next.y1] = 1;
				q.push(next);
			}
		}

		// 가로 모양일때
		if (now.direction == 0) {
			for (int i = 1; i < 4; i += 2) {
                // 회전이 가능한가
				if (checkRotate(now.x1 + dir[i][0], now.y1 + dir[i][1], now.x2 + dir[i][0], now.y2 + dir[i][1])) {
                    // 왼쪽이 축일 경우
					if (!visited[now.x1][now.y1][now.x1 + dir[i][0]][now.y1 + dir[i][1]]) {
						robot next(now.x1, now.y1, now.x1 + dir[i][0], now.y1 + dir[i][1], 1, now.count + 1);
						visited[next.x1][next.y1][next.x2][next.y2] = 1;
						visited[next.x2][next.y2][next.x1][next.y1] = 1;
						q.push(next);
					}
                    // 오른쪽이 축일 경우
					if (!visited[now.x2][now.y2][now.x2 + dir[i][0]][now.y2 + dir[i][1]]) {
						robot next(now.x2, now.y2, now.x2 + dir[i][0], now.y2 + dir[i][1], 1, now.count + 1);
						visited[next.x1][next.y1][next.x2][next.y2] = 1;
						visited[next.x2][next.y2][next.x1][next.y1] = 1;
						q.push(next);
					}
				}
			}
		}
		else if (now.direction == 1) {// 세로 모양일때
			for (int i = 0; i < 3; i += 2) {
                // 회전이 가능한가
				if (checkRotate(now.x1 + dir[i][0], now.y1 + dir[i][1], now.x2 + dir[i][0], now.y2 + dir[i][1])) {
                    // 아래가 축일 경우
					if (!visited[now.x1][now.y1][now.x1 + dir[i][0]][now.y1 + dir[i][1]]) {
						robot next(now.x1, now.y1, now.x1 + dir[i][0], now.y1 + dir[i][1], 0, now.count + 1);
						visited[next.x1][next.y1][next.x2][next.y2] = 1;
						visited[next.x2][next.y2][next.x1][next.y1] = 1;
						q.push(next);
					}
                    // 위가 축일 경우
					if (!visited[now.x2][now.y2][now.x2 + dir[i][0]][now.y2 + dir[i][1]]) {
						robot next(now.x2, now.y2, now.x2 + dir[i][0], now.y2 + dir[i][1], 0, now.count + 1);
						visited[next.x1][next.y1][next.x2][next.y2] = 1;
						visited[next.x2][next.y2][next.x1][next.y1] = 1;
						q.push(next);
					}
				}
			}
		}
	}

	return -1;
}