[백준] 1525번: 퍼즐 (C++ 풀이)

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

풀이

1. 단순히 생각하면 퍼즐 단계 단계 BFS로 탐색하면 되지만, 3X3배열을 저장해놓아야 한다는 메모리적인 부담이 있다.

이 문제는 메모리제한이 32MB이기 때문에 배열을 저장하는 것은 옳지 않다.

그래서 생각해낸것이 string으로 저장하는 것이다.

결국에는 이 문자열이 "123456780"이 되면 펴즐이 완성이 되는 것이다.

 

2. 큐에 현재문자열과 걸린 시간을 저장한다. 현재 문자열에 대해서 이제 처리를 하면되는데,

관건은 0의 위치다. 0의 상하좌우에 있는 숫자들은 0으로 이동할 수 있기 때문이다.

string에 있는 find함수로 '0'을 찾고, 상하좌우를 탐색해주기 위해서 3X3배열일때 0의 (x, y)좌표를 계산을 통해 찾는다.

x=0의 위치 / 3이고, y=0의 위치 % 3 이다. 

 

3. set<string>을 써서 탐색한 퍼즐에 대해서 또 탐색하지 않도록

set에 현재문자열이 있는지 체크하고 없으면 set에 문자열을 넣어둔다.

 

4. 큐를 빠져나와도 목적을 찾지 못하면 -1을 출력한다.

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1525.cpp

결과