[백준]1525 - 퍼즐

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

1525번: 퍼즐

 

흥미로운 문제였다.

 

2차원 배열 형태의 격자를 1차원 형태의 문자열처럼 만들고, map 자료구조를 이용해서 방문 체크를 할 수 있다.

원래는 빈 칸 주위의 숫자들을 빈칸으로 이동하면서 퍼즐을 맞추지만,

조금 더 편리하게 구현하기 위해 빈칸이 이동하는 것으로 생각해서 dx, dy 기법을 편리하게 이용할 수 있었다.

 

#include <iostream>
#include <map>
#include <queue>
using namespace std;
map<string, int> m;
int main() {
	string s = "";
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			char c; cin >> c;
			s += c;
		}
	}
	queue<string> q;
	q.push(s);
	m[s] = 1;
	int x[4] = { 0,0,1,-1 };
	int y[4] = { 1,-1,0,0 };
	while (!q.empty()) {
		string s = q.front();
		q.pop();
		if (s == "123456780") {
			cout << m[s] - 1;
			return 0;
		}
		int idx = s.find('0');
		int i = idx / 3;
		int j = idx % 3;
		for (int k = 0; k < 4; k++) {
			int nx = i + x[k];
			int ny = j + y[k];
			if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
				string t = s;
				char temp;
				temp = t[idx];
				t[idx] = t[nx * 3 + ny];
				t[nx * 3 + ny] = temp;
				if (m.find(t) == m.end()) {
					q.push(t);
					m[t] = m[s] + 1;
				}
			}
		}
	}
	cout << -1;
}