[백준][BFS] 1039번 교환

문제

정수 N이 주어졌을 때 M이 정수자릿수라면 1<= i < j <= M 인 i, j를 골라서 i번 위치와 j번의 위치를 바꿉니다. 이러한 교환을 K번 했을 때 나올 수 있는 최댓값을 구해야합니다.

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

풀이

처음엔 살짝 조건을 착각했는데 교환할 수 없는 조건은 맨 앞자리 수가 0이 되는 경우뿐이고, 그렇지 않을 때는 i<j 인 i, j 위치끼리 교환이 가능합니다. 여기서 K번 연산을 할 수 없는 경우라는 조건이 있기 때문에 만약 i번째 자리와 j번째가 같더라도 연산은 할 수 있기때문에 교환작업을 해줘야합니다.(만약 숫자가 같은 경우 바꾸지 않도록 해주어서 틀렸습니다를 받았습니다.) 처음에 동일한 숫자가 되는 경우가 가능하지 않다고 생각을하고 visited 배열을 만들었는데 동일한 숫자가 같은 단계에서는 큐에 넣을 필요가 없고 연산 횟수가 다를 때 나타난 경우에는 이미 나타난 숫자도 큐에 넣을 수 있어야 합니다. 중복이 된다고 생각해서 visited를 사용하지 않았더니 메모리 초과가 났습니다. 그래서 한 단계마다 새로 큐를 만들어서 중복되지 않도록 해주었습니다.(또는 단계마다 큐를 초기화해주는 것과 같습니다.) 이렇게 큐에서 한단계씩 빼내는 작업은 K번했을 때 가장 큰 숫자를 저장해서 출력하면 됩니다. 만약 K번 작업을 하지 않았는데 큐가 비었다는 것은 더이상 교환 연산을 할 수 없다는 뜻이므로 -1을 출력해줍니다.

코드

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