[백준] 1525 퍼즐 C++

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

1525번: 퍼즐

 

---

후기

조금 어려웠던점 점은 원본 상태에 대한 상태를 변경해야한다는 부분을 어떻게 처리할 줄 몰랐었습니다.

기존의 조금 까다롭다고 생각되는 문제들은 2차원 배열을 탐색하는 것이 아니라 값 자체를 탐색하는것에 추가적으로 특정 상태를 기억한다음에 탐색을 이어 가는데 해당 문제는 이 두가지 가 모두 포함된 상태에서 탐색을 하는 대상자체와 방문 표시를 하는 부분에 대한 신경도 썻어야 하는 문제입니다.

---

풀이 

"103425786"에 대한 상태를 문자열로 관리를 해줍니다.

'0'이 있는 인덱스를 찾아 행과열을 구해주고 왼쪽, 아래, 오른쪽, 위쪽 으로 스왑이 가능한지 살펴본뒤 가능하다면 스왑을 해주고 현재 상태를 저장합니다.

이때 다음 탐색을 이어가기 전에 방문배열을 std::set으로 관리하며 log(N)으로 빠르게 방문 여부를 확인해야합니다.

그러다 목표상태인 "123456780"이 만족되는 상태가 나오면 탐색을 종료하고 정답을 출력합니다.

---

코드

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <queue>
#include <limits.h>
#include <memory.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;

#define endl "\n"
#define ll long long

set<string> visit;
int ret = -1;

string Start;
string End = "123456780";

int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1 };

bool CanGo(int x, int y)
{
	if (x >= 0 && x < 3 && y >= 0 && y < 3) return true;
	return false;
}

void BFS()
{
	queue<pair<string, int>> q;
	q.push(make_pair(Start, 0));
	visit.insert(Start);

	while (!q.empty())
	{
		auto now = q.front(); q.pop();
		string str = now.first;
		int cnt = now.second;
		
		if (strcmp(str.c_str(), End.c_str()) == 0)
		{
			ret = cnt;
			return;
		}

		int idxOfZero = str.find('0');
		int y = idxOfZero / 3;
		int x = idxOfZero % 3;
		
		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (CanGo(nx, ny))
			{
				string tmp = str;
				swap(tmp[y * 3 + x], tmp[ny * 3 + nx]);
				if (visit.find(tmp) == visit.end())
				{
					visit.insert(tmp);
					q.push(make_pair(tmp, cnt + 1));
				}
			}
		}
	}
}

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

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			char c; cin >> c;
			Start += c;
		}
	}

	BFS();
	cout << ret << endl;
	
	return 0;
}