백준 C++ 1525 퍼즐

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

1525번: 퍼즐

BFS를 이용해 퍼즐을 풀 수 있습니다. 0의 위치를 기준으로 BFS를 돌리면 됩니다. 하지만 메모리가 아주 작기 때문에 배열이 아닌 string을 활용해 map의 키로 활용하여 해당 string이 조회되었는지 확인합니다. 

 

코드는 다음과 같습니다.

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

using namespace std;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 }; // 상하좌우
char puzzle[3][3];
map<string, bool>check; // 해당 문자열 만든 적 있는 지 확인
int result; // 최종 결과
int X, Y;

void init()
{
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> puzzle[i][j];
			if (puzzle[i][j] == '0') {
				X = j;
				Y = i;
			}
		}
	}
	result = 987654321;
}

void change_puzzle(int nx, int ny, int x, int y) {

	puzzle[y][x] = puzzle[ny][nx];
	puzzle[ny][nx] = '0';

}
string puzzle_to_string() {

	string s = "";

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			s += puzzle[i][j];
		}
	}
	return s;
}

void string_to_puzzle(string s) {

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			puzzle[i][j] = s[i * 3 + j];
		}
	}
}

void bfs()
{
	queue<pair<pair<int, string>, pair<int,int>>> q;

	string st = puzzle_to_string();

	q.push({ { 0, st }, {Y, X} });

	while (!q.empty()) {

		int num = q.front().first.first;
		string s = q.front().first.second;
		int y = q.front().second.first;
		int x = q.front().second.second;

		q.pop();

		if (s == "123456780")
			result = min(result, num);

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

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

			string_to_puzzle(s);
			change_puzzle(nx, ny, x, y);
			string s2 = puzzle_to_string();
		
			if (check[s2] == true)
				continue;

			check[s2] = true;
			q.push({ {num + 1, s2 }, {ny, nx} });
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	init();
	bfs();
	if (result == 987654321)
		cout << -1;
	else
		cout << result;
}