백준 1525. 퍼즐

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

1525번: 퍼즐

 

이 문제는 목표 상태에 도달하는 최소 횟수를 구해야 하기 때문에 bfs를 돌리면 된다.

그런데 이 문제의 핵심은 bfs의 중복 처리다. 

bfs는 중복되는 경우 큐에 넣지 않도록해서 반복되지 않도록 해줘야 한다.

 

위와 같이 주어졌을때  bfs를 돌린다고 생각하면 우선 [0][1]의 자리를 주위의 1 or 2 or 3 숫자와 자리를 바꿀것이다. 

만약 1이랑 바꾼다고 하면 다음 상태가 된다.

 

0	1	3
4	2	5
7	8	6

 

그런데 여기서 다음으로 0과 1을 다시 바꾸려고 할것이다. 

그렇게 되면 원 상태로 돌아가고 무한히 반복하게 된다.

따라서 이미 검사한 상태는 검사하지 않도록 해야 하는데 위 [3][3] 크기의 배열을 예를들어 벡터에 넣는다고 하면 벡터의 크기는 점점 커지고 검사 시간도 엄청나게 길어질것이다. 

 

이 문제는 map 자료구조를 사용하면 된다.

위 상태를 문자열로 바꿔서 map에 바꾼다. 

위 상태를 문자열로 바꾸면 "013425786" 이 될것이고 map["013425786"] = true 이런식으로 해주고, map에 해당 key값이 있으면 검사하지 않으면 된다.

 

그리고 문자열이 "123456780" 이 되면 우리가 원하는 목표값에 도달한 것이다.