백준 1525번 퍼즐

- 문제 설명

 

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

 

정리된 퍼즐을 만들기 위해 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

 

* 퍼즐이 정리된 상태

1 2 3

4 5 6

7 8 

 

 

- 입력

 

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

 

 

- 출력

 

1) 첫째 줄에 최소의 이동 횟수를 출력한다.

 

*이동이 불가능한 경우 -1을 출력한다.

 

 

* 문제 풀이의 핵심

 

 

1. BFS

 

이 문제는 퍼즐의 빈칸을 채우기 위해 상하좌우의 퍼즐칸을 이동시키는 문제로 생각하게 된다면 정리된 퍼즐을 만드는 최단 거리 검색 문제로 바꿀 수 있습니다.

 

모든 경로를 다 검색한다고 가정하면 한 칸당 9 개의 숫자가 올 수 있기 때문에 모든 경우의 수는 9! (= 362880) 이며 한정된 시간내에 모든 경우의 수를 탐색할 수 있습니다.

 

퍼즐의 빈 칸을 인접한 칸의 숫자로 채우면서 퍼즐이 정리가 되었는지 확인하는 방식으로 계속 이동하다 보면 정리된 퍼즐을 찾을 수 있습니다.

 

 

2. 알고리즘

 

<1> 입력 변경

 

숫자의 입력을 3*3 형태의 2차원 배열로 받을 수도 있지만 9자리로 이루어진 하나의 숫자로 생각해 볼 수도 있습니다.

 

ex1) 빈칸이 0 인 경우

1 0 3            =>          103425786

4 2 5

7 8 6

 

하지만, 빈 칸이 0 인 경우 첫 째 자리가 0 일 때 처리가 쉽지 않기 때문에 빈 칸을 숫자 0 이 아닌 9 로 바꿔서 생각하면 쉽습니다.

 

ex2) 빈칸이 9 인 경우

9 1 3            =>          913425786

4 2 5

7 8 6

 

 

for (int i = 0; i < 9; i++) {
  int num;
  cin >> num;
  if (num == 0) num = 9;
  start = start * 10 + num;
}

 

 

* 퍼즐 배열에 따른 경우의 수를 map 으로 나타내야 하는 이유

 

퍼즐 배열은 36만개 정도에 9 자리 숫자로 이루어져 있습니다. 그렇다면 int 형 배열을 사용해서 숫자를 저장하려면 다음과 같습니다.

 

int puzzle[999999999];

 

이 정도 크기의 배열을 32 MB 의 크기제한으로는 해결할 수 없습니다.

 

그래서 퍼즐 배열을 키로하고 퍼즐 배열일 때 이동한 횟수를 값으로 설정한 map 을 선언하면 공간복잡도를 줄일 수 있습니다.

 

ex)

map<int,int> m;

m[123456789] = 3;

 

 

<2> 퍼즐의 배열 변경

 

그렇다면 퍼즐을 3*3 배열이 아닌 int 형 숫자로 변경했다면, 빈 칸을 인접숫자로 채우기 쉽게 만들기 위해 문자열로 변경해줍니다.

 

문자열로 변경했을 때, 빈 칸(숫자 9) 의 3*3 행렬로 퍼즐이 배치되어 있을 때의 y, x 위치를 나누기, 나머지 연산으로 쉽게 찾을 수 있습니다.

 

ex) 빈 칸의 y, x 좌표 구하기 (0, 1)

1 0 3            =>          193425786

4 2 5

7 8 6

 

이 때 9 는 문자열의 1 번째 인덱스에 존재하며 y, x 의 좌표는 y = (1 / 3) = 0, x = (1 % 3) = 1 과 같은 식으로 구할 수 있습니다.

 

 

string s_cur = to_string(cur);

int z = s_cur.find('9');
int y = z / 3;
int x = z % 3;

 

 

<3> BFS 탐색

 

이제 3*3 퍼즐의 빈 칸 인덱스를 알았으니 인접한 숫자와 자리를 교체해주면 됩니다.

 

빈 칸으로 숫자를 이동시킨다는 것이 swap 연산을 하는 것과 같은 의미이기 때문입니다.

 

BFS 탐색 시 퍼즐 배열을 만든적이 없다면 탐색을 해야하므로 .count() 함수를 사용해 map 에 해당 키 값이 이미 존재하는 지 검사하고 존재하지 않는다면 (0) 다음 경우를 탐색하도록 만들면 됩니다.

 

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<queue>
#include<tuple>
#include<map>

using namespace std;

// (y,x) : 상 하 좌 우
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };

int bfs(int start) {
	int cnt = 0;

	queue<int> q;
	q.push(start);

	map<int, int> dist;
	dist[start] = 0;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		string s_cur = to_string(cur);

		int z = s_cur.find('9');
		int y = z / 3;
		int x = z % 3;

		for (int i = 0; i < 4; i++) {
			int ny = y + dir[i][0];
			int nx = x + dir[i][1];

			if (ny < 0 || ny >= 3 || nx < 0 || nx >= 3) continue;

			int before = y * 3 + x;
			int after = ny * 3 + nx;

			string temp = s_cur;
			swap(temp[before], temp[after]);

			int next = stoi(temp);
			if (dist.count(next) == 0) {
				q.push(next);
				dist[next] = dist[cur] + 1;
			}
		}
	}

	if (dist.count(123456789) == 0) {
		return -1;
	}
	else {
		return dist[123456789];
	}
}

int main() {
	int start = 0;
	
	for (int i = 0; i < 9; i++) {
		int num;
		cin >> num;
		if (num == 0) num = 9;
		start = start * 10 + num;
	}

	cout << bfs(start) << "\n";
}

 

 

 

- 문제링크 : www.acmicpc.net/problem/1525

1525번: 퍼즐

 

 

- 제출한 코드

 

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요