[백준]Baekjoon1525(queue)

문제링크 : https://www.acmicpc.net/problem/1525

풀이

이 문제의 핵심은 2차원 배열을 마치 1차원 배열처럼 생각하고 문제를 풀어야한다는 점이다.

이렇게 한 이유는 이차원 배열을 통해 bfs로 문제를 풀었을 때

이미 했던 경우의 수를 check하기가 까다롭기 때문이다.

만약 이차원 배열이 아니라 문제에 있는 

이런 퍼즐을 193425786 (0은 9로 바꿔서 넣음) 으로 생각하고 문제를 풀 때 

map을 이용하면 방문했는지 여부와 횟수가 어떻게 되는지를 동시에 알 수 있다.

아래의 코드와 주석을 보면 어떻게 풀었는지 이해할 수 있을것이다.

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

using namespace std;

int move_x[] = { 1,-1,0,0 };
int move_y[] = { 0,0,1,-1 };

int main()
{
	int start = 0; 
	int answer = 0; //이동 횟수
	bool b = false;

	int num;
	for (int i = 0; i < 9; i++) {
		scanf("%d", &num);
		if (num == 0) num = 9;
		start = start * 10 + num; 
	} //퍼즐의 상태를 1차원으로 생각하여 숫자로 저장하는 과정

	map<int, int> m;
	m[start] = 0;
	queue<int> q;
	q.push(start);

	while (!q.empty())
	{
		int number = q.front(); //큐의 맨 앞에있는 숫자
		q.pop();
		string str = to_string(number); //숫자를 string형으로 변환
		answer = m[number];
		int index = str.find('9'); //9의 index 탐색
		if (index == 8) { //9가 맨 마지막에 있을 때 
			if (str.substr(0, 8) == "12345678") {//퍼즐이 제대로 맞춰져 있다면
				b = true; break;
			}
		}
		int x = index / 3; //행
		int y = index % 3; //열

		for (int i = 0; i < 4; i++) {
			int nx = x + move_x[i];
			int ny = y + move_y[i];
			if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
				int move = 3 * nx + ny; //2차원 index를 1차원 index로 변환해주는 과정
				string tmp = str;
				swap(tmp[index], tmp[move]);
				int result = stoi(tmp);
				if (m[result] == 0) {
					q.push(result);
					m[result] = answer + 1;
				}
			}
		}
	}
	b ? printf("%d\n", answer) : printf("%d\n", -1);
}