백준 1039번 교환

< 백준 1039번 교환 - 마포 코딩박 >

사용한 알고리즘: BFS


 N자리 숫자가 주어지고, 이 숫자의 i번째와 j번째를 바꾸는 것을 K번 했을때 나올 수 있는 최대 숫자를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) (코드: 63~64)
 주어진 숫자가 1자리 수이거나, 2자리수이면서 뒷자리가 0인 경우 조건에 의해 바꾸는 행동을 할 수 없습니다. 이때 -1 을 출력합니다.

(2) (코드: 8~15)
 string으로 받은 숫자를 int로 변환해주는 함수를 하나 만들어줍니다.

(3) (코드: 17~57)
 x번 바꾼 숫자를 저장할 queue를 만듭니다.
 처음에는 0번 바뀐 (처음 입력받은) 숫자를 queue에 넣어줍니다.
 queue에 들어있는 x번 바뀐 모든 수를 꺼내 각 수의 모든 가능한 i<->j 바꾸기를 해준 후 다시 queue에 저장합니다.
 ( 이후 queue에는 x+1번 바뀐 모든 수가 들어있게됩니다.)

(4) (코드: Visit, 27줄)
 과정 (3)을 진행하며, set<string> 을 만들어 중복해서 저장하는 것을 피합니다.

(5) (코드: 43,44)
 K번 바뀐 수 중 최대를 답으로 출력합니다.