[2020카카오공채] 블록 이동하기

https://programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

BFS를 이용해서 푸는 문제!

멍청하게 DFS로 풀었다가 시간초과가 떴다.

.. 덕분에 같은 실수 두번은 하지 않을 것 같다.

 

탐색한 결과를 저장할 배열로 이차원 배열인 way_h, way_v를 선언했다.

아니면 3차원 배열로 선언해줘도 되고..

 

상, 하, 좌, 우로 움직이는 경우와 회전하는 경우를 모두 일일히 코딩해줘야 하기 때문에 구현 실수하기 딱 좋은 문제이다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

#define MAX_NUM	1000000

int solution(vector<vector<int>> board) {
	int answer = 0;

	vector<vector<int>> way_h;
	vector<vector<int>> way_v;

	int b_size = board.size();

	// way 세팅
	way_h.resize(b_size);
	way_v.resize(b_size);
	for (int i = 0; i < b_size; i++) {
		way_h[i].resize(b_size, MAX_NUM);
		way_v[i].resize(b_size, MAX_NUM);
	}

	queue<tuple<bool, int, int, int>> q;
	q.push(make_tuple(1, 0, 0, 0));

	while (!q.empty()) {
		bool shape = get<0>(q.front());
		int x = get<1>(q.front());
		int y = get<2>(q.front());
		int i = get<3>(q.front());
		q.pop();

		// 가로인 경우
		if (shape) {
			if (x < 0 || y < 0 || x >= b_size || y >= b_size - 1) continue;
			if (board[x][y] || board[x][y + 1]) continue;
			if (way_h[x][y] <= i) continue;

			way_h[x][y] = i;
			i++;

			// 회전하는 경우
			if (x - 1 >= 0 && !board[x - 1][y] && !board[x - 1][y + 1]) {
				q.push(make_tuple(0, x - 1, y, i));
				q.push(make_tuple(0, x - 1, y + 1, i));
			}
			if (x + 1 < b_size && !board[x + 1][y] && !board[x + 1][y + 1]) {
				q.push(make_tuple(0, x, y, i));
				q.push(make_tuple(0, x, y + 1, i));
			}

			// 움직이는 경우
			q.push(make_tuple(1, x - 1, y, i));
			q.push(make_tuple(1, x + 1, y, i));
			q.push(make_tuple(1, x, y - 1, i));
			q.push(make_tuple(1, x, y + 1, i));
		}

		// 세로인 경우
		else {
			if (x < 0 || y < 0 || x >= b_size - 1 || y >= b_size) continue;
			if (board[x][y] || board[x + 1][y]) continue;
			if (way_v[x][y] <= i) continue;

			way_v[x][y] = i;
			i++;

			// 회전하는 경우
			if (y - 1 >= 0 && !board[x][y - 1] && !board[x + 1][y - 1]) {
				q.push(make_tuple(1, x, y - 1, i));
				q.push(make_tuple(1, x + 1, y - 1, i));
			}
			if (y + 1 < b_size && !board[x][y + 1] && !board[x + 1][y + 1]) {
				q.push(make_tuple(1, x, y, i));
				q.push(make_tuple(1, x + 1, y, i));
			}

			// 움직이는 경우
			q.push(make_tuple(0, x - 1, y, i));
			q.push(make_tuple(0, x + 1, y, i));
			q.push(make_tuple(0, x, y - 1, i));
			q.push(make_tuple(0, x, y + 1, i));
		}
	}

	answer = min(way_h[b_size - 1][b_size - 2], way_v[b_size - 2][b_size - 1]);

	return answer;
}