1525번: 퍼즐

문제 설명

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

1525번: 퍼즐

[문제]

  3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

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

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

 가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

 

[입력]

  세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

 

[출력]

  첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

 

[예제 입력 1]

1 0 3
4 2 5
7 8 6

[예제 출력 1]

3

[예제 입력 2]

3 6 0
8 1 2
7 4 5

[예제 출력 2]

-1

---

풀이

 문제 자체에서 요구하는 알고리즘은 어렵지 않지만, 알맞은 자료구조 선정이 핵심이었던 문제이다. 문제 자체에서 원하는 탐색은 퍼즐을 맞춰가는 것으로, 일종의 경로 이동이라 생각하면 '0'이라 있는 지점에서 상, 하, 좌, 우로 이동하며 해당 위치의 값과 값을 스왑해 나가면 된다. 그렇게 계속 탐색을 진행하며 전체적인 퍼즐 모양이 정렬되면, 그 때의 탐색 횟수를 반환하면 되고 그렇지 못하다면 -1을 반환하면 된다.

 하지만 BFS 탐색 기반으로 코드를 짜기 위해선 큐에 현재 정보들을 넣어야 하고, 탐색 중복 여부를 판별할 자료구조도 필요하다. 심지어 이 문제에서는 현재 전체적인 퍼즐 모양이 모두 정보로 필요하고 탐색의 종료 조건 또한 전체 퍼즐을 다 확인해야 하기 때문에 많은 공간을 요구한다. 그렇기에 퍼즐을 2차원 배열이나 벡터로 구성하고 이를 계속 큐에 넣어 탐색을 진행한다면 공간의 문제도 있고 탐색 중복 여부의 자료구조 선정도 애매해진다.

 그렇게 대안으로 생각한 것이 퍼즐을 길이 9 짜리의 string 형태로 받아내는 것이었다. 이렇게 되면 탐색을 진행할 때 필요한 큐와 탐색 중복 여부에 필요한 자료구조가 단순히 string 뿐이고, string의 경우 인덱스로 접근이 가능하기에 상하좌우 이동도 인덱스를 잘 조절하면 충분히 수행가능하다. 또한 탐색의 종료조건인 퍼즐의 정렬 상태가 string으로 표현하면 "123456780"이기 때문에, 종료 조건 비교도 매우 간단해진다.

 탐색 중복 여부를 판단하는 자료구조의 경우 처음에는 unordered_set을 활용하여 코드를 작성했고, 이후 시간을 줄여보기 위해 string 퍼즐의 int 변형을 인덱스로 하는 배열로 했으나 이는 메모리 초과로 실패했다.

 

#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;
unordered_set<string> visited;//중복 여부

struct infor {//상태 정보 구조체
	string puzzle;
	int r, c, times;
};

int search(string puzzle, int startR, int startC) {
	queue<infor> q;
	q.push({ puzzle, startR, startC, 0 });

	while (!q.empty()) {
		infor now = q.front(); q.pop();
		string nowPuzzle = now.puzzle;
		int nowR = now.r;
		int nowC = now.c;
		int nowTimes = now.times;
		char a, b;

		if (visited.find(nowPuzzle) != visited.end())//이미 해본 방법이라면 pass
			continue;

		if (nowPuzzle == "123456780")//맞게 풀었다면
			return nowTimes;

		visited.insert(nowPuzzle);//중복 여부 표시

		++nowTimes;
		a = nowPuzzle[3 * nowR + nowC];//현 위치 char 저장

		if (nowR > 0) {//위쪽 이동
			b = nowPuzzle[3 * nowR + nowC - 3];
			nowPuzzle[3 * nowR + nowC - 3] = a;
			nowPuzzle[3 * nowR + nowC] = b;

			q.push({ nowPuzzle, nowR - 1, nowC, nowTimes });

			nowPuzzle[3 * nowR + nowC - 3] = b;
			nowPuzzle[3 * nowR + nowC] = a;
		}

		if (nowR < 2) {//아래쪽 이동
			b = nowPuzzle[3 * nowR + nowC + 3];
			nowPuzzle[3 * nowR + nowC + 3] = a;
			nowPuzzle[3 * nowR + nowC] = b;

			q.push({ nowPuzzle, nowR + 1, nowC, nowTimes });

			nowPuzzle[3 * nowR + nowC + 3] = b;
			nowPuzzle[3 * nowR + nowC] = a;
		}

		if (nowC > 0) {//왼쪽이동
			b = nowPuzzle[3 * nowR + nowC - 1];
			nowPuzzle[3 * nowR + nowC - 1] = a;
			nowPuzzle[3 * nowR + nowC] = b;

			q.push({ nowPuzzle, nowR , nowC - 1, nowTimes });

			nowPuzzle[3 * nowR + nowC - 1] = b;
			nowPuzzle[3 * nowR + nowC] = a;
		}

		if (nowC < 2) {//오른쪽이동
			b = nowPuzzle[3 * nowR + nowC + 1];
			nowPuzzle[3 * nowR + nowC + 1] = a;
			nowPuzzle[3 * nowR + nowC] = b;

			q.push({ nowPuzzle, nowR, nowC + 1, nowTimes });

			nowPuzzle[3 * nowR + nowC + 1] = b;
			nowPuzzle[3 * nowR + nowC] = a;
		}
	}

	return -1;
}

int main() {
	string puzzle = "", temp;
	int startR, startC;

	for (int i = 0; i < 3; i++) {//초기화
		for (int j = 0; j < 3; j++) {
			cin >> temp;
			if (temp == "0") {
				startR = i;
				startC = j;
			}
			puzzle += temp;
		}
	}

	cout << search(puzzle, startR, startC);

	return 0;
}

---

결과