[백준]1525 퍼즐

문제

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

풀이

보드 자체가 탐색할 노드가 되어야 한다는 생각을 하기 어려웠다.

처음엔 보드에서 0을 움직이고 현재 보드가 정렬된 상태인지 검사하며 탐색할 생각을 했으나, 퍼즐을 가장 빠르게 푸는 방법을 생각해내지 못했다.

이 문제는 보드의 상태마다 0을 움직일 수 있는 경우의 수가 인접한 노드로 존재하는 그래프를 떠올리고, 모든 숫자가 제자리에 위치한 상태의 노드를 탐색해야하는 문제였다.

 

보드는 vector<int>에 저장했다.

탐색에는 BFS알고리즘을 이용했다. 그 이유는 가장 빠르게 퍼즐을 푸는 방법을 찾는 문제였기 때문에, 0의 움직임이 적은 경우의 수 부터 모두 체크할 수 있는 BFS가 적합하다고 판단했기 때문이다.

BFS의 큐는 queue<pair<vector<int,int>,int>>에 {보드, 깊이}를 삽입해 이 보드가 0을 몇 번 움직인 상태인지 알 수 있게 했다.

알고리즘을 간단히 설명하면 아래와 같다.

1. 시작 상태의 보드를 큐에 삽입함.

2. 큐에서 보드와 깊이 정보를 꺼냄.

3. 꺼낸 보드가 정렬되어있다면 깊이값을 반환함.

4. 아니면 0이 움직일 수 있는 칸을 찾고, 해당 칸으로 움직였을 때의 임시 보드를 만듦.

5. 임시 보드를 큐에 삽입함.

6. 2~6을 반복

7. 큐가 비어있다면 -1 반환.

 

 

코드

// CodeTest.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

//위 아래 좌 우
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
vector<int> board(9);
vector<int> rightBoard{1,2,3,4,5,6,7,8,0};

int Find0(const vector<int>& _board)
{
	for (size_t i = 0; i < 9; i++)
	{
		if (_board[i] == 0)
			return i;
	}
	return -1;
}
pair<int, int> ToRC(int idx)
{
	return { idx / 3, idx % 3 };
}
int ToIdx(pair<int, int> pos)
{
	return pos.first * 3 + pos.second;
}
bool CanGo(int r, int c)
{
	if (r > 2 || r < 0
	|| c > 2 || c < 0)
		return false;

	return true;
}
int BFS()
{
	queue<pair<vector<int>, int>> q;
	set<vector<int>> isVisited;
	isVisited.insert(board);
	q.push({ board ,0});
	while (q.empty() == false)
	{
		vector<int> curBoard(q.front().first);
		int depth = q.front().second;
		q.pop();

		if (curBoard == rightBoard)
			return depth;

		int cur0Idx = Find0(curBoard);
		pair<int, int> cur0Pos = ToRC(cur0Idx);

		for (size_t i = 0; i < 4; i++)
		{
			int nR = cur0Pos.first + dr[i];
			int nC = cur0Pos.second + dc[i];
			int nIdx = ToIdx({ nR,nC });

			if (false == CanGo(nR, nC))
				continue;

			vector<int> tmp(curBoard);
			swap(tmp[nIdx], tmp[cur0Idx]);

			if (isVisited.find(tmp) != isVisited.end())
				continue;

			isVisited.insert(tmp);
			q.push({ tmp, depth +1 });
		}
	}
	return -1;
}
int main()
{
	
	for (size_t i = 0; i < 9; i++)
	{
		int input; cin >> input;
		board[i] = input;
	}
	cout << BFS();
}