백준1525 퍼즐 - C++

굉장히 유명한 퍼즐이다.

이거.. 논란이 좀 있었던 문제인데

내부 사정이니 그러려니 하고 넘어간다..

 

1.모든 경우의 수를 미리 계산 해놓고

주어진 상황에 맞는 수를 뱉는 방식이 있고,

2.완전탐색을 통해 제일 빠르게 원상태가 만드는 방식이 있고

3.손으로 풀듯이 최적의 방향으로 가산점을 부여하면서 움직일 수도 있겠다.

 

가장 쉬운 방식인 2번이.. 이번에 핫이슈였으므로

2번으로 완전탐색한다.

#include <iostream>
#include <queue>
#include <string>
#include<map>
using namespace std;
int dy[] = { 0,-1,1,0 };
int dx[] = { -1,0,0,1 };

queue <int >q1;
map <int, int> visited;

#define initstate  123456789

//완전탐색
int findZero(string Map) {
	for (int i = 0; i < 9; i++) {
		if (Map[i] == '9') return i;
	}
}

//모든 경우의수 탐색 숫자기반
int sol(int start) {
	q1.push(start);
	visited[start] = 0;
	while (!q1.empty()) {
		int cur = q1.front();
		q1.pop();
		if (cur == initstate) return visited[cur];
		//printmap(cur);
		string tmp = to_string(cur);
		int zeroidx = findZero(tmp);
		// 바꿀 수 있는 위치 from zeroidx
		int zero_y = zeroidx / 3;
		int zero_x = zeroidx % 3;
		for (int i = 0; i < 4; i++) {
			tmp = to_string(cur);
			int ny = zero_y + dy[i];
			int nx = zero_x + dx[i];
			if (ny < 3 && ny >= 0 && nx < 3&& nx >= 0) {
				tmp[zeroidx] = tmp[3 * ny + nx];
				tmp[3 * ny + nx] = '9';
				int next = stoi(tmp);
				if (!visited[next]) {
					visited[next] = visited[cur] + 1;
					q1.push(next);
				}
					
				
			}
		}

	}


	return -1;
}


int main() {
	int start = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			start *= 10;
			int tmp = 0;
			scanf("%d", &tmp);
			if (tmp == 0) tmp = 9;
			start += tmp;
		}
	}
	int ans = sol(start);
    
	printf("%d", ans);
}