[백준][BFS] 9019번 DSLR

문제

숫자 A, B가 주어질 때 주어진 4개의 명령을 최소한으로 적용시켜 A를 B로 변환해야합니다. 최소한으로 필요한 명령어 나열을 출력해야합니다. 

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

풀이

최소한의 명령을 통해 변환해야하므로 BFS를 통해서 큐에 넣으면서 한단계동안 수행할 수 있는 숫자를 만들어봅니다. D, S, L, R 각 명령어를 수행하는 함수를 만들었고, 큐에서 pop한 값을 차례대로 넣으면서 새로운 숫자가 만들어지면 해당하는 숫자를 또 큐에 넣습니다. 만약 최소한의 명령개수를 구하는 거라면 더 쉽게 생각할 수 있었을텐데 해당 명령어를 나열하는 것이 답이기 때문에 조금 고민을 했습니다. 큐에서 pop한 수를 4개의 명령어를 다 수행시켜보고 변환된 숫자가 이미 나오지 않았다면 해당 숫자가 어떤 명령어를 통해서 만들어진건지 기록을 하고, 어떤 숫자에서 변환이 된건지를 기록합니다. check[만들어진 숫자] = 만들기 전 숫자 를 해주고, dir[만들어진 숫자] = D or S or L or R을 기록합니다. 이렇게 되면 마지막 숫자가 만들어졌을 때 check[만들어진 숫자] 에서 제일 처음 입력된 A까지 찾아갈 수 있고 찾아가면서 해당 dir을 벡터에 넣은다음 역순으로 출력하게 되면 만들어진 명령어 나열이 완성됩니다. D, S, L, R 계산을 잘 해주고 출력하기 위해 저장을 잘 해주면 됩니다! 참고로 테스트케이스가 여러개이다보니까 초기화를 해줘야했는데 check, dir 배열을 전부 다 초기화해주기에는 너무 시간이 많이 낭비되는 것 같아서 한 테스트케이스마다 사용된 숫자만을 벡터에 저장하고, BFS가 종료될 때 벡터의 숫자 check, dir만 초기화해주도록 하였습니다.

모르고 역순으로 출력해서 틀린 다음 다시 도전.. 떨리는 순간..

코드

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