[백준/c++] 1525번 - 퍼즐

문제

1525번: 퍼즐

풀이

분류 : 완전탐색

 

0만 3x3 위치로 옮기는게 아니라, 퍼즐판까지

1 2 3

4 5 6

7 8 0

순으로 맞춰야 하는 것이 이 문제의 핵심이었습니다. + bfs

결국 입력값을 123456780의 순서로 만들수 있는지를 체크하면 되었습니다.

 

1. 입력값을 string 문자열로 초기화하되, 0은 9로 치환해줍니다.

2. 처음 입력받은 문자열을 큐에 넣어줍니다.

3. 큐에서 pop한 문자열에서 9의 위치를 찾고, 9와 상하좌우를 스왑합니다.

4. 스왑으로 새로 만들어진 string문자열이, 캐시의 key로 이미 등록되어있는지 체크합니다.

5. 등록되지 않은 경우, 새로 만들어진 string문자열을 다시 큐에 넣습니다.

6. while(!q.empty())일때까지 반복.

 

코드(O(nm)) *O(nm)이 아니라면 알려주세요. 감사합니다(--)(__)*

	#include <iostream>
	#include <map>
	#include <queue>
	#include <algorithm>
	#include <string>
	#define WH 3
	#define MAX 9
	using namespace std;
	int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
	string TARGET = "123456789";
	int main() {
	int p[WH][WH];
	string chk;
	for (int i = 0; i < WH; i++) {
	for (int j = 0; j < WH; j++) {
	cin >> p[i][j];
	if (p[i][j] == 0) p[i][j] = 9;
	chk += to_string(p[i][j]);
	}
	}
	queue<string> q;
	map<string, int> visited;
	q.push(chk);
	visited[chk] = 0;
	while (!q.empty()) {
	string curChk = q.front();
	q.pop();
	if (curChk == TARGET) break;
	else {
	int empty = curChk.find('9');//9위치 찾음
	int x = empty/3, y = empty%3;
	for (int i = 0; i < 4; i++) {//상하좌우 움직일수 있는곳 찾음
	int nx = x + dir[i][0], ny = y + dir[i][1];
	if (nx >= 0 && nx < WH && ny >= 0 && ny < WH) {
	//9와의 위치와 스왑
	string temp = curChk;
	swap(temp[x*3+y], temp[nx*3+ny]);
	//map에 이미 temp가 있는지 확인, 없으면 큐에 추가
	if (!visited.count(temp)) {
	visited[temp] = visited[curChk] + 1;
	q.push(temp);
	}
	}
	}
	}
	}
	if (!visited.count(TARGET)) cout << -1 << endl;
	else cout << visited[TARGET] << endl;
	return 0;
	}

view raw 백준_1525_퍼즐.cpp hosted with ❤ by GitHub