[BOJ 1525] 퍼즐

문제 출처 : www.acmicpc.net/problem/1525

 

풀이 :

 

BFS 문제입니다.

 

메모리 제한이 24메가로 작습니다

그렇기에 9개의 칸을 0~8의 값인지 9차원 배열로 판단할 시에 메모리 초과가 뜨게 됩니다.

그렇기에 [3][3] 배열을 long long 형 변수에 매핑시켜 그 값을 중복 체크 하시면 됩니다.

 

	#include<iostream>
	#include<vector>
	#include<queue>
	#include<algorithm>
	#include<unordered_set>
	using namespace std;
	typedef long long ll;
	typedef pair<ll, int> p;
	int mp[3][3], dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 }, x, y;
	ll a, num, goal = 123456780;
	unordered_set<ll> s;
	int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	////////////////////////////////////////////////////////
	//////////map 정보를 long long 형 값으로 매핑/////////////
	////////////////////////////////////////////////////////
	for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++) {
	cin >> a;
	num = num * 10 + a;
	};
	if (num == goal) {
	cout << 0;
	return 0;
	}
	////////////////////////////////////////////////////////
	/////////////////중복 검사를 위해 SET 사용////////////////
	////////////////////////////////////////////////////////
	s.insert(num);
	queue<p> q;
	q.push({ num,0 });
	bool chk = false;
	while (q.size()) {
	p nowp = q.front();
	ll now = nowp.first;
	q.pop();
	////////////////////////////////////////////////////////
	////////long long 형 값을 다시 [3][3]배열로 매핑//////////
	////////////////////////////////////////////////////////
	mp[2][2] = now % 10;
	mp[2][1] = (now / 10) % 10;
	mp[2][0] = (now / 100) % 10;
	mp[1][2] = (now / 1000) % 10;
	mp[1][1] = (now / 10000) % 10;
	mp[1][0] = (now / 100000) % 10;
	mp[0][2] = (now / 1000000) % 10;
	mp[0][1] = (now / 10000000) % 10;
	mp[0][0] = (now / 100000000) % 10;
	for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)if (mp[i][j] == 0)y = i, x = j;
	for (int k = 0; k < 4; k++) {
	int ny = y + dy[k], nx = x + dx[k];
	if (ny < 0 || nx < 0 || ny == 3 || nx == 3)continue;
	ll pushnum = 0;
	int tmp = mp[y][x];
	mp[y][x] = mp[ny][nx];
	mp[ny][nx] = tmp;
	for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)pushnum = pushnum * 10 + mp[i][j];
	tmp = mp[y][x];
	mp[y][x] = mp[ny][nx];
	mp[ny][nx] = tmp;
	if (s.find(pushnum) != s.end())continue;
	s.insert(pushnum);
	if (pushnum == goal) {
	chk = true;
	cout << nowp.second + 1;
	break;
	}
	q.push({ pushnum, nowp.second + 1 });
	}
	}
	if (!chk)cout << "-1";
	}

view raw 1522.cpp hosted with ❤ by GitHub