[백준/C++] 1525번 퍼즐 풀이

문제 해석

---

---

문제 풀이

---

종이에 끄적여보니 0을 바꾸는 순서와 숫자의 위치에 관계를 찾기에는 어려움이 있었고

 

BFS로 브루트포스처럼 모든 나갈 수 있는 경우의 수를 보기에는

체크해야하는 배열이 9⁹개라서 10억에 가까운 배열을 생성하기엔 어려움이 있어 보였다.

 

그렇다면 map에 필요한만큼 넣고 순서를 잘 백트래킹형식으로 작성해주면 되겠다고 생각했는데

그냥 int를 넣기에는 어려움이 있어서 1차원으로 flatten한 이후 string으로 변환시켜주었다.

 

그리고 문제에는 함정이 존재하는데 flatten해서 1차원 배열로 계산하는 경우

4번째칸에서 3번째칸으로 7번째칸에서 6번째칸으로 이동이 불가능하다

---

코   드

---

#include <bits/stdc++.h>
using namespace std ;
const string want = "123456780" ; //우리가 찾고 싶어하는 문자열
vector<int> puzzle(9) ;
map<string, int> mp ;
int way[] = {1, -1, -3, 3} ; // 0이 이동할 수 있는 방향은 flatten했을 때 이와 같다.

int BFS()
{
	queue<string> que ;
	string start ;
    
	for(int& it : puzzle)
		start +=  it + '0' ; //문자열로 변환
	
	que.push(start) ;
	while(!que.empty())
	{
		string front = que.front() ;
		que.pop() ;
		if(front == want) return mp[front] ;

		int idx = 0 ;

		for( ; idx < front.size() ; idx++) 
			if(front[idx] == '0') break ; // 0 위치 찾아내기

		for(int i = 0 ; i < 4 ; i++)
		{
			string new_str = front ;
			if(idx + way[i] < 0 || idx + way[i] > 8) continue ; //기준 사이즈 초과 방지
			if(i == 0 && (idx + way[i]) / 3 > idx / 3) continue ;// 3,6번칸에서 4,7번 넘어감 방지
			if(i == 1 && (idx + way[i]) / 3 < idx / 3) continue ;// 4, 7에서 3,6 칸 넘어감 방지

			swap(new_str[idx], new_str[idx + way[i]]) ; //새로운 문자열
			
			if(mp[new_str] == 0)
			{
				mp[new_str] = mp[front] + 1 ; //백트래킹을 위해 기록
				que.push(new_str) ;
			}
		}
	}

	return -1 ;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0) ;
	for(int& it : puzzle)
		cin >> it ;

	cout << BFS() ;
}

---

느낀점: 뭔가 map과 string으로 변환만 생각하면 크게 어려운 문제는 아니였던 것 같다.

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

1525번: 퍼즐