JUST WRITE IT. HomeArchivesTagsCategories
백준 1525번 퍼즐
|AlgorithmBOJ|

1525. 퍼즐

Problem

Solution

  • 상당히 어려운 문제다. (접근법을 알아둘 필요가 있다.)
  • 접근법
  1. 2차원 배열을 1차원 배열로 생각하기
  2. 퍼즐에 적혀있는 숫자를 하나로 쭉 이어진 수로 생각한다.
  3. 이어진 수 하나가 경우의 수라고 생각한다. (문제 목표는 123456789인 수(경우)를 찾는 것)
  4. map<해당 경우(수), 이동 횟수>를 사용하여 해당 경우에 도달하기까지 걸리는 이동 횟수를 저장한다.
  5. 9(0)이 있는 위치에서 시작하여 BFS 탐색을 하고 탐색 시에 swap을 해야 한다. (이동을 할 때 인덱스 계산에 주의한다.)
  6. swap을 위해 string을 사용한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    ex) 현재 193425786 (0대신 9를 해야 각 자릿 수가 모두 채워진다. 0123...으로 하면 0이 사라짐)
    193425786 
    -> 913425786 (왼쪽 이동)
    -> 123495786 (아래쪽 이동)
    -> 149425786 (오른쪽 이동)

    3 x 3 
    0 1 2
    3 4 5
    6 7 8
    행 = 9번 위치(0~8 중) / 3
    열 = 9번 위치 % 3
  • 주의

아래 코드에서 dist.count(next_num) == 0 대신 dist[next_num] == 0 을 하면 틀리다.
dist[해당 수]에는 이동 횟수가 들어있고 dist.count(해당 수)는 해당 경우의 수가 몇 번 나왔는지 알려주기 때문이다. map에서 해당 키, 값을 넣어주지 않았는데 바로 해당 키에 대한 값을 참조하려고(dist[next_num] == 0) 하면 제대로 연산이 수행되지 않을 것이다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
queue<int> q;
map<int, int> dist;
void BFS(int start) {
	q.push(start);
	dist[start] = 0;
	while (!q.empty()) {
		int now_num = q.front();
		q.pop();
		string now = to_string(now_num);
		int zero = now.find('9'); // 0의 위치
		int x = zero / 3; // 행
		int y = zero % 3; // 열
		for (int dir = 0; dir < 4; ++dir) {
			int d_x = x + dx[dir];
			int d_y = y + dy[dir];
			if (d_x > -1 && d_y > -1 && d_x < 3 && d_y < 3) {
				string next = now;
				swap(next[x * 3 + y], next[d_x * 3 + d_y]); // 문자열 인덱스(2차원->1차원)
				int next_num = stoi(next);
				if (dist.count(next_num) == 0) {
					q.push(next_num);
					dist[next_num] = dist[now_num] + 1;
				}
			}
		}
	}
}
int main() {
	string s = "";
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			int num; cin >> num;
			if (num == 0) num = 9;
			s += to_string(num);
		}
	}
	int start = stoi(s);
	BFS(start);
	if (dist.count(123456789) == 0) cout << -1 << "\n";
	else cout << dist[123456789] << "\n";
	return 0;
}
Algorithm