백준 1525: 퍼즐

문제 요약

3×3 표에 수가 채워져 있다. 한 칸은 반드시 비워져 있다.

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 최소 이동 횟수를 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• BFS
• 해시를 사용한 집합과 맵

문제 풀이

BFS로 풀면 된다. 퍼즐을 알맞게 풀기 위해 걸리는 최소 이동시간을 구하는건데, 여기서 BFS로 탐색하여 풀 수 있다. 입력에서의 자료형은 int인 2차원 배열로 주어지지만, 큐에 넣어서 탐색을 하려면 배열을 사용하기보다 다른 자료구조를 사용하는 것이 낫다. vector나 string 등을 사용할 수 있지만, 나는 string으로 구현하였다. 방문 여부를 확인해야 하기 때문이다.

여기서 2차원 배열이 아닌 string을 사용했기때문에, 상호간에 서로 변환하는 작업이 필요하다.
3x3 2차원 배열을 왼쪽 위에서부터 오른쪽 아래 순차적으로 0~8까지 번호를 부여하고, 각 번호로 늘어뜨려서 새로운 string을 얻는다.

즉, 2차원 배열의 한 위치를 (i, j)라고 한다면, 해당 위치의 번호는 i * 3 + j가 된다. 또한 어떠한 번호 t에 대하여 해당 t의 2차원 위치는 다음과 같이 구할 수 있다.

i = t / 3, j= t % 3

숫자의 이동은 0, 즉 비어있는 위치로만 할 수 있으므로 먼저 0의 위치를 구해야한다. string에서의 0의 위치를 알아내고, 이 위치를 통해 2차원 좌표를 구해낸다.

이렇게 알아낸 0의 2차원 좌표값을 바탕으로 상하좌우를 탐색하면 된다. 여기서 visited배열로 방문 여부를 파악하는 것이 힘든데, 여기서 set자료구조를 사용하면 된다.

set의 find()를 이용하여 중복 여부를 검사하였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

using namespace std;

const int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0 } };
queue<string> q;
set<string> visited;

int main()
{
	int in, level = -1, qsize, pos, posx, posy, nx, ny;
	string temp = "", next;
	bool sol = false;
	for (int i = 0; i < 9; i++) {
		scanf("%d", &in);
		temp += '0' + in;
	}
	q.push({ temp , 0 });
	visited.insert(temp);

	while (!q.empty()) {
		level++;
		qsize = q.size();
		while (qsize--) {
			temp = q.front();
			if (temp == "123456780") {
				printf("%d", level);
				return 0;
			}
			q.pop();
			pos = temp.find('0');
			posx = pos % 3;
			posy = pos / 3;
			for (int i = 0; i < 4; i++) {
				nx = posx + dir[i][1];
				ny = posy + dir[i][0];
				if (nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2) {
					next = temp;
					swap(next[pos], next[ny * 3 + nx]);
					if (visited.find(next) == visited.end()) {
						visited.insert(next);
						q.push(next);
					}
				}
			}
		}		
	}
	printf("-1");
	return 0;
}

후일담

비주얼 스튜디오에서 디버깅하여 콘솔창에 테스트했을때는 결과가 나오기까지의 시간이 너무 오래 걸려서 시간을 최대한으로 아낀 이런저런 방법들로 시도하여 제출하였지만 결국 모두 실패했다.

그런데 그냥 거의 처음의 아이디어로 제출하니까 성공했다. 콘솔에서 시간이 오래걸린다고 낙담하지 말자.