백준 1525번 퍼즐

 

 

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

 

 

DFS나 BFS로 풀려고 했으나 visit처리를 어떻게 해야하는지 고민이였다.

결론은 각 넘버의 순서를 한줄로 만들어서 map으로 visit 처리하면 됨.

DFS로 풀면 map에서 스택 오버플로우 생기므로, BFS로 품.

그리고 이미 정렬된 상태에서 0을 출력해야 하는 예외도 처리.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
using namespace std;

int arr[3][3];
map<int, int> visit;
bool flag = false;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };



int main(void)
{
	int y, x;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> arr[i][j];
		}
	}

	int idx = 100000000;
	int start = 0;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (!arr[i][j])
			{
				start += idx * 9;
			}
			else
			{
				start += idx * arr[i][j];
			}
			idx /= 10;
		}
	}
	queue<int> que;
	que.push(start);
	visit[start] = 0;

	while (!que.empty())
	{
		int num = que.front();
		que.pop();

		if (num == 123456789)
		{
			break;
		}

		string temp = to_string(num);
		int z = temp.find('9');
		int y = z / 3;
		int x = z % 3;

		for (int i = 0; i < 4; i++)
		{
			int newy = y + dy[i];
			int newx = x + dx[i];
			string cal = temp;
			if (newy >= 0 && newy < 3 && newx >= 0 && newx < 3)
			{
				swap(cal[3 * y + x], cal[3 * newy + newx]);
				int new_num = stoi(cal);
				if (!visit[new_num])
				{
					visit[new_num] = visit[num] + 1;
					que.push(new_num);
				}
			}
		}


	}
	if (visit.count(123456789) != 0 )
	{
		cout << visit[123456789] << endl;
	}
	else
	{
		cout << -1 << endl;
	}

}