백준 1039. 교환

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

1039번: 교환

 

bfs 문제인데 시간초과가 나지 않도록 처리해야 하는 문제다.

다음 예제를 보자 

 

132 3

N=132, K=3 이다.

우선 문제에서 주어진 조건대로 숫자들을 움직여보면 

 

                                   132                                                   // depth = 0

                      /                |                 \                                  

               312                231               123                            // depth = 1

          /    |     \             /     |     \           /     |      \   

    132  213  321    321  132  213    213  321  132            // depth = 2

 

이런식으로 나오게 되는데 깊이 2를 보면 중복되는 숫자들이 생긴다. 

이걸 처리 안해주게 되면 큐의 크기가 점점 늘어나서 시간초과가 된다. 

 

해결방법은 각 깊이 마다 이미 처리된 숫자들을 기록해놓고 다시 방문하지 않도록 하면 된다. 

 

그리고 숫자를 string형태로 저장하고, 대소비교도 그대로 진행했는데 어처피 비교하는 모든 문자의 크기는 N.size()로 동일하기 때문에 int 형으로 바꾸고 비교하지 않아도 된다.