[백준 9019] DSLR [Python]

백준 9019 - 문제

백준 9019 - 입/출력

---

풀이

두 수 A, B가 주어질 때 문제에서 정의된 D, S, L, R 명령을 사용해서 A를 B로 만드는 과정에서 사용한 명령을 순서대로 출력해주면 된다.

시간 제한은 6초로 넉넉한 편이기 때문에 Bidirectional Search 방식을 사용하지 않고, 기본 BFS 방식으로도 해결할 수 있다.

 

우선, 동일한 숫자가 만들어져 중복된 탐색을 방지하기 위해, 해당 숫자를 만들지 않은 경우에만 만들어줘야한다.

queue에 해당 숫자를 만들기 위한 명령어를 set으로 묶어 넣어줘도 되지만, visited 배열에 넣어주기로 했다.

단 위의 방식을 사용할 경우 boolean값이 아닌, 문자열이 탐색 기준이 되기 때문에, 초기값과는 분명히 다른 시작값을 넣어주어야 한다. (초기값 : '-', 시작값 : '')

queue에 들어간 숫자를 한 개씩 받아서 각 명령에 맞는 숫자를 next_val에 생성했다.

 

생성한 숫자를 살펴보며 만들고자 하는 숫자(B)와 일치하면 기존의 숫자(val)까지 만들기 위한 명령어와 생성한 숫자를 만들기 위해 사용한 명령어( 'DSLR' [idx] )을 이어 붙여 반환해주면 된다.

만약 일치하지 않은 숫자인 경우, 이미 만든적이 없는 경우 초기값 '-' 과 비교해 생성한 숫자를 만들기 위한 명령어를 visited 배열에 넣어주고, queue에 생성한 숫자를 넣어 다음 탐색을 진행해주면 된다.

 

A와 B가 동일한 경우와 정답이 없는 경우는 없으니, 결국 답이 나오기 때문에 추가로 전처리 해주어야 하는 과정은 없다. 

---

소스코드

소스코드 보기

---

출처

9019번: DSLR