백준 1697: 숨바꼭질 (Swift)

어떤 알고리즘을 적용해서 풀이할지 바로 떠오르지 않았던 문제이다.

처음에는 DP를 사용해야하는 것인지 고민했었다.

 

그렇게 DP로 구현하는 과정을 머리로 떠올려보니,

5에서 출발하여 17까지  ( +1, -1, *2 ) 이 세가지 연산을 적용해가며 도달하는 과정을 떠올려보니

이들 모두를 계속 Check할 boundary에 담아두고 계속 위의 세가지의 연산을 적용해 뻗어나가야했고,

그렇다면 DP가 아닌 queue를 이용한 bfs로 접근하는 것이 좋겠다고 판단했다.

방문했던 숫자는 또 방문할 필요가 없으므로 visited 배열을 선언하여 체크해주었다.