(프로그래머스) 게임 맵 최단거리

문제 링크

• 프로그래머스

요약

• BFS에서 set을 이용한 visited 처리는 최후의 수단이다.

최종 §

결과

• 그냥 BFS돌리면 되는데, 주의할 점은 visited처리를 단순하게 set으로 구현 하면 timeout이 난다.

#include <vector>
#include <queue>
#include <set>
 
using namespace std;
 
#define PACK_XY(x, y) ((((x) & 0xFF) << 8) | ((y) & 0xFF))
#define PACK(step, x, y) (((step) << 16) | PACK_XY(x, y))
#define UNPACK_STEP(pack) (((pack) >> 16) & 0xFFFF)
#define UNPACK_X(pack) (((pack) >> 8) & 0xFF)
#define UNPACK_Y(pack) ((pack) & 0xFF)
 
constexpr int delta[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
int solution(vector<vector<int>> maps)
{
	int X = maps.size();
	int Y = maps[0].size();
	queue<int> q;
 
	q.push(PACK(1, 0, 0));
	maps[0][0] = 0;
 
	while (!q.empty()) {
		int pack = q.front();
		int step = UNPACK_STEP(pack);
		int x = UNPACK_X(pack);
		int y = UNPACK_Y(pack);
		q.pop();
 
		if (x + 1 == X && y + 1 == Y) {
			return step;
		}
 
		for (int i = 0; i < 4; i++) {
			int new_x = x + delta[i][0];
			int new_y = y + delta[i][1];
 
			if (0 <= new_x && new_x < X && 0 <= new_y && new_y < Y) {
				if (maps[new_x][new_y]) {
					q.push(PACK(step + 1, new_x, new_y));
					maps[new_x][new_y] = 0;
				}
			}
		}
	}
 
	return -1;
}

삽질 기록 §

코드

#include <vector>
#include <queue>
#include <set>
 
using namespace std;
 
#define PACK_XY(x, y) ((((x) & 0xFF) << 8) | ((y) & 0xFF))
#define PACK(step, x, y) (((step) << 16) | PACK_XY(x, y))
#define UNPACK_STEP(pack) (((pack) >> 16) & 0xFFFF)
#define UNPACK_X(pack) (((pack) >> 8) & 0xFF)
#define UNPACK_Y(pack) ((pack) & 0xFF)
 
constexpr int delta[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
int solution(vector<vector<int>> maps)
{
	int X = maps.size();
	int Y = maps[0].size();
	queue<int> q;
	set<short> visited;
 
	q.push(PACK(1, 0, 0));
	visited.insert(PACK_XY(0, 0));
 
	while (!q.empty()) {
		int pack = q.front();
		int step = UNPACK_STEP(pack);
		int x = UNPACK_X(pack);
		int y = UNPACK_Y(pack);
		q.pop();
 
		if (x + 1 == X && y + 1 == Y) {
			return step;
		}
 
		for (int i = 0; i < 4; i++) {
			int new_x = x + delta[i][0];
			int new_y = y + delta[i][1];
 
			if (0 <= new_x && new_x < X && 0 <= new_y && new_y < Y) {
				if (maps[new_x][new_y]) {
					if (visited.find(PACK_XY(new_x, new_y)) == visited.end()) {
						q.push(PACK(step + 1, new_x, new_y));
						visited.insert(PACK_XY(new_x, new_y));
					}
				}
			}
		}
	}
 
	return -1;
}

• Set으로 visited처리를 했을때 코드. Timeout난다.
• 그리고 코드가 날라가서 여기에 적지는 못했는데, bms두개로 visited처리하는 것은 불가능하다.
  • bms 두개 써서 두개 모두 켜졌을 때만 visited인 것으로 구현하려고 했는데, 안된다.
  • 왜냐면 bms를 키는 것이 하나의 줄을 전부 마킹하는 셈이기 때문.
  • 예를들어 [2, 0] 와 [0, 3] 을 방문했다고 했을 때 x=2 와 y=3 이 모두 bms에 의해 마킹되기 때문에 [2, 3] 은 방문하지도 않았는데 방문했다고 판단해버린다.