[백준][BFS] 1525번 퍼즐

문제 

0은 비어있는 칸을 의미하고, 1~9까지 적힌 3*3 배열이 들어왔을 때 비어있는 칸으로 인접한 숫자들을 이동시키며 1, 2, 3, 4, 5, 6, 7, 8, 0 과 같은 정렬된 상태를 만드시오. 이 때 최소한의 이동횟수를 출력하고 만약 불가능하면 -1을 출력하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1525)

풀이

최소한의 이동횟수를 구해야하므로 큐를 사용해서 BFS를 써야겠다고 생각했습니다. 그런데 한번 큐를 pop했을 때 가능한 이동이 최대 4번인데 이 때 모든 이동했을 때마다 각 배열을 어떻게 저장해둬야할지 고민됐습니다. 일단 문제를 풀어보고자 struct 에서 3*3 배열을 선언해주어서 큐에 넣어봤습니다. 수행하다보니 큐사이즈가 엄청 커지게 되고, 중복을 체크해줄 수 없다는 문제점이 있었습니다. 0~8칸 중에 같은 자리가 비더라도 다른 자리에 적힌숫자는 다르기 때문에 이 3*3 배열자체를 중복체크할 방법이 없었습니다. 그래서 저장방법을 바꿔야했는데 잘 떠오르지 않아 질문검색을 참고했습니다. 0~8까지 들어오는 input을 하나의 int형 숫자로 만들어주면 쉽게 해결할 수 있었습니다. 예제에서 1 0 3, 4 2 5, 7 8 6 이렇게 3줄이 들어오는데 하나의 숫자 103425786으로 변환시켜주면 int형을 넣는 큐를 만들어주면 되고 map을 써서 방문해줬는지를 쉽게 체크해줄 수 있었습니다.(너무나 똑똑한 사람이 많네요..) 자리를 이동시키기위해서는 비어있는 칸(0인 칸)이 어디인지 알아야하므로 /와 %를 적절히 사용해서 구해줍니다. 그리고 옆의 칸은 -1, +1 인 자리일 것이고 위아래는 -3, +3인 칸일 것입니다. 여기서도 범위를 잘 체크해줘야하는데 인덱스 계산을 통해 0보다 작아지거나 8보다 커지면 빈칸 교환을 할 수 없습니다. 그리고 더 주의해야하는 점은 자리를 0부터 지정해줬을 때 2번과 3번은 바꿀 수 없고 5번과 6번도 바꿀 수 없습니다. 계산으로는 +1, -1이 범위를 벗어나지 않아서 체크해줘야 합니다! 이 부분에서 체크를 바로 떠올리지 못해서 제출 전에 반례 케이스를 찾아보다가 고쳤습니다. 배열로 입력이 들어오지만 int형 하나의 숫자로 바꿔주는 부분, visit 체크, 자리를 바꿀 때 예외적인 케이스를 고려해준다면 문제를 해결할 수 있습니다!

+ while문의 조건이 큐가 empty일 경우와 찾지 못한 경우(!found) 였는데 이후 정답을 출력할 때 큐가 비어있을 때 찾지 못했다고 -1을 출력해서 틀렸습니다를 받았습니다. (found돼서 break 될 경우에는 큐가 당연히 차있을거라 생각해서 따로 수정을 안했는데 큐가 다 비어있고 found되는 경우에 while문을 빠져나올 때가 있어서 정답이 있는데도 큐가 비어있어서 -1을 출력하는 경우도 있나봅니다.)

코드

https://github.com/kswim/Algorithm/blob/master/BFS/1525.cpp