[G2] 백준 1525번 퍼즐 C++ 우선순위 큐, 해시맵

리뷰

 

3 * 3크기의 퍼즐을 정렬된 상태로 만드는 최단 시간을 구하는 문제

https://www.acmicpc.net/problem/1525

 

 

전역 변수

• lst : 초기 퍼즐 정보를 저장할 정수형 2차 배열
• v : 퍼즐의 상태를 방문처리 하기 위한 해시맵
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 퍼즐의 현재 상태를 정의하기 위한 구조체, 좌표 위치  x, y와 현재 맵 정보 b, 현재까지 소요 시간 t로 구성되며 t를 기준으로 오름차순 정렬한다.

 

함수

1. bfs

int bfs(const Pos& start)

 

너비 우선 탐색을 통해 퍼즐이 정렬되기 까지 걸리는 최소 시간을 구하는 함수

1. 매개변수로 초기 퍼즐 정보 start를 전달받는다.
2. Pos타입의 우선순위 큐 q를 초기화 하고, start를 q에 push해준다.
3. 시작 퍼즐 위치 정보를 해시맵 v의 key로 방문처리를 진행해 준다.
4. 정렬이 완료된 상태의 값을 변수 target에 저장해 준다.
5. q가 빌 때 까지 while루프를 수행해 주고, 매 루프마다 요소를 한개씩 꺼내어 준다.
6. 현재 위치 cx, cy와 현재 맵 정보 cb, 소요시간 ct로 구조체 내 변수를 파싱해 준다.
7. 기저 조건으로 cb가 target에 도달하였다면 ct를 리턴해 준다.
8. 4방향 탐색을 진행하며 맵의 범위 안에 있다면 이동을 진행해 준다.
9. 변수 nf에 이동하고자 하는 위치의 값을 파싱해 준다.
10. 변수 nb에 이동하고자 하는 위치의 값을 빼주고, 현재 위치에 해당 값을 추가해 준다.
11. 만약 nb가 방문처리 되어 있다면 continue처리해 준다.
12. 방문처리 되지 않았다면 방문처리 후 q에 이동 위치와 변경된 맵, 소요 시간을 증가시켜 push해준다.
13. while루프가 종료될 때 까지 기저 조건에 도달하지 못한 경우 -1을 리턴해 준다.

 

문제풀이

1. 초기 퍼즐의 정보를 저장할 Pos타입의 변수 pos를 초기화 해준다.
2. 정수형 변수 bits를 0으로 초기화 해준다, 해당 변수에 초기 맵 정보를 저장해줄 예정이다.
3. 3 * 3크기의 맵 정보를 입력 받는다, 만약 0이 입력된 경우 pos에 해당 위치를 초기화 해주고 continue해준다.
4. bits에 현재 좌표의 값을 10에 제곱하고 번호를 곱한 만큼의 값을 더해준다.
5. 입력을 모두 받은 후 pos의 b에 bits값을 저장해 준다.
6. bfs함수에 pos를 매개변수로 전달하고 리턴값을 출력해 준다.

 

트러블 슈팅

1. 3 * 3크기 이므로 최대 2^10 - 1크기의 변수로 비트마스킹을 진행하려 했으나 2의 제곱수가 존재하여 포기했다.
2. 맵을 변경하지 않은 상태에서 맵 정보를 체크하기 위해 9자리의 정수로 표현이 가능했다.

 

참고 사항

• 정렬된 상태를 87654321로 정의하였다, 각 자릿수를 맵 상에서 3 * i + j의 인덱스 좌표로 매핑하였다.
• 따라서 예제 1번의 초기 맵은 687524301이며, 예제 2번의 초기 맵은 5472180653이다.
• 이동할 위치에 저장된 값을 구해놓고, 현재 위치를 해당 값으로, 이동할 위치를 0으로 변경해 주었다.
• 범위가 최대 10^9 - 1이므로 방문 상태를 처리하려면 배열이 아닌 해시맵을 통해 구현해 주어야 한다.

 

정답 코드

#include<iostream>
#include<queue>
#include<cmath>
#include<unordered_map>
using namespace std;

int lst[3][3];
unordered_map<int, bool> v;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y, b, t;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};

int bfs(const Pos& start) {
	priority_queue<Pos> q;
	q.push(start);
	v[start.b] = 1;
	int target = 87654321;

	while (!q.empty()) {
		Pos pos = q.top(); q.pop();
		int cx = pos.x, cy = pos.y, cb = pos.b, ct = pos.t;
		if (cb == target) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;
			if (0 <= nx && nx < 3 && 0 <= ny && ny < 3) {
				int nf = cb / (int)pow(10, 3 * nx + ny) % 10;
				int nb = cb - (int)pow(10, 3 * nx + ny) * nf + (int)pow(10, 3 * cx + cy) * nf;
				if (v[nb]) continue;
				v[nb] = 1;
				q.push({ nx, ny, nb, nt });
			}
		}
	}
	return -1;
}

int main() {
	Pos pos;
	int bits = 0;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> lst[i][j];
			if (!lst[i][j]) {
				pos = { i, j, 0, 0 };
				continue;
			}
			bits += pow(10, 3 * i + j) * lst[i][j];
		}
	}
	pos.b = bits;
	cout << bfs(pos);
}