[백준/BOJ] 백준 1525번 : 퍼즐

www.acmicpc.net/problem/1525

1525번: 퍼즐

board상황을 숫자로 표현하여 map<int, int> discovered; (보드, depth)로 discovered를 나타내서 문제를 해결했다.

 

코드

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

int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//보드 상황을 숫자로 표현한다
int board_to_number(vector<vector<int>> board)
{
	string s_number = "";

	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
		{
			s_number += to_string(board[i][j]);
		}

	return stoi(s_number);
}

//숫자를 보드로 표현한다
vector<vector<int>> number_to_board(int number)
{
	string s_number = to_string(number);
	vector<vector<int>> ret(3, vector<int>(3, 0));

	if (s_number.size() < 9)
	{
		s_number = '0' + s_number;
	}

	int cnt = 0;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
		{
			string temp = "";
			temp += s_number[cnt];
			ret[i][j] = stoi(temp);
			cnt++;
		}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	map<int, int> discovered; //(보드, depth)
	queue<int> q;
	vector<vector<int>> start_board(3, vector<int>(3, 0));
	vector<vector<int>> dest_board(3, vector<int>(3, 0)); //목표 상태 저장

	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
		{
			int input;
			cin >> input;

			start_board[i][j] = input;
		}

	int cnt = 1;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
		{
			dest_board[i][j] = cnt;
			cnt++;
		}
	dest_board[2][2] = 0;

	int start_number = board_to_number(start_board);
	int dest_number = board_to_number(dest_board);

	q.push(start_number);
	discovered.insert(make_pair(start_number, 0));

	while (!q.empty())
	{
		int here_number = q.front();
		vector<vector<int>> here_board = number_to_board(here_number);
		q.pop();

		//목표 상태랑 같을때
		if (here_number == dest_number)
		{
			cout << discovered[here_number];
			return 0;
		}

		pair<int, int> zero;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
			{
				if (here_board[i][j] == 0)
					zero = make_pair(i, j); //빈칸의 위치를 찾는다
			}

		//빈칸의 주변 4곳을 확인
		for (int i = 0; i < 4; i++)
		{
			pair<int, int> near = make_pair(zero.first + dxdy[i][0], zero.second + dxdy[i][1]);

			//주변이 보드 안에 있을때
			if (near.first >= 0 && near.first < 3 && near.second >= 0 && near.second < 3)
			{
				vector<vector<int>> there_board(here_board);

				//there_board는 주변칸을을 기존의 빈칸으로 옮긴것 
				there_board[zero.first][zero.second] = here_board[near.first][near.second];
				there_board[near.first][near.second] = 0;

				int there_number = board_to_number(there_board);

				//발견된적이 없을때
				if (discovered.count(there_number) == 0)
				{
					discovered.insert(make_pair(there_number, discovered[here_number] + 1));
					q.push(there_number);
				}
			}
		}
	}

	cout << -1;


	return 0;
}