Baekjoon(백준) 9019번 - DSLR

백준 사이트의 9019번.
문제 제목 : DSLR
백준 9019

ICPC Regionals Korea Nationwide Internet Competition 2011 D번

문제 해석

문제에 직관적으로 설명되어 있어서 딱히 해석을 더 할 건 없다.

풀이 전략

BFS search를 하면 된다. (만약 dfs로 한다면 어디까지 search 해야 할지가 불분명하기 때문에 bfs로 탐색해야 한다) 또한, bfs search는 사용한 operation 개수가 적은 숫자부터 탐색이 진행되기 때문에 타겟인 숫자를 가장 먼저 찾았을 때 그 때까지 사용된 operation을 순서대로 추적해서 출력하면 된다. (문제에 보면 필요한 최소한의 명령어 나열을 출력하라고 되어 있다) cycle을 방지하고 시간을 아끼려면 이미 탐색한 숫자는 그 다음에 다시 탐색하지 않도록 처리해주어야 한다.

구현

풀이전략에서 설명했듯이 bfs search를 이용하므로 while 문과 queue를 사용해서 구현하면 된다. 또한, 가능한 숫자가 10000 미만이므로 visited number를 check하는 array를 이용하면 된다. 문제는 타겟 넘버를 찾으면 처음부터 그 타겟넘버까지 도달하는데 적용된 operation을 순서대로 모두 찾아야 한다는 것이다. dfs 같으면 recursive function의 return 값과 특성을 활용해서 역추적이 쉽게 가능하겠지만 bfs는 그렇지 않다.
나는 처음에 코드를 작성할 때 queue에 push 할 때 그 숫자를 만들기 위해서 적용된 모든 operation을 같이 기록하였다. 즉, 해당 숫자 (int)와 operation을 기록한 array (vector<int>) 를 매번 queue에 push 하고 operation을 적용해서 새로운 숫자를 만들면 operation 기록 array를 통째로 복사하고 해당 Operation 을 push해서 다시 queue 에 넣고… 이런 방식으로 했다는 뜻이다. 꽤 생각없이 짠 것이라 할 수 있다. 자신있게 제출했더니 바로 시간 초과 떴다. 원인을 알 때까지 꽤 생각을 많이 했는데 기본적인 것을 잊고 있었다. array 크기가 커질수록 그 array 전체에 대해서 코드에서 손을 대면 (ex. 복사 등) 그 만큼 더 오랜 시간이 걸린다. 따라서, operation을 기록하는 방식을 바꿀 필요가 있다.
queue는 계속 앞의 숫자를 pop 해주어야 하므로 나중에 역추적 을 하기에는 부적절하다. 모든 숫자를 기록하는 data 가 하나 있다. 바로 visited number 를 체크하는 array 다. 나는 이 array에 각각 그 숫자가 되기 바로 전 숫자, 바로 전 숫자에서 이 숫자로 넘어올 때 적용된 operation을 기록했다. 그리고 target number를 찾으면 visited number check array 를 참조해서 시작 number까지 역추적해서 operation을 모두 출력할 수 있었다.

자세한 솔루션 코드는 github에 있다. 한 번 코드를 중간에 갈아엎는 바람에 파일명 main_new.cpp 가 최종 정답 코드이다.

baekjoon 9019 solution code