[백준, 1697번] 숨바꼭질 (BFS, 너비 우선 탐색, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 숨바꼭질" 문제는 수빈(N)이와 동생(K)의 위치가 주어질 때 동생을 찾을 수 있는 가장 빠른 시간을 출력하는 문제입니다.

• 수빈이는 걷거나 순간이동을 할 수 있다.
• 수빈이의 위치가 x라면
  • 걷기 : x + 1, X -1 
  • 순간이동 : x * 2

즉, 수빈이가 동생을 찾을 수 있는 최단 시간을 구하는 것이기 때문에 BFS 문제의 대표적인 형태입니다.

---

트리 계층도

위와 같이 시작 노드에서 시작해서 수빈이가 이동할 수 있는 위치를 탐색하고, 최단시간이니깐 BFS를 사용하여 해결합니다.

 

각 위치에서 수빈이는 1초 후에 X-1, X+1, X*2로 이동할 수 있으며, Time이 증가할 때마다 모든 가능한 위치를 큐에 넣어 순서대로 탐색합니다.

 

이렇게 BFS로 탐색하면 처음 목표 위치(동생의 위치)에 도달했을 때가 항상 최단 시간이 됩니다.

---

위 트리 계층도대로 예제 입력을 표현하자면 다음과 같습니다.

 

위와 같이 수빈이의 위치(5)에서 시작해서 레벨 단위로 수빈이가 탐색할 수 있는 위치를 큐에 넣고, 동생의 위치인 17을 찾을 때까지 BFS로 탐색합니다.

 

각 시간(Time)마다 큐에서 위치를 꺼내서 -1, +1, ×2 연산 을 통해 이동할 수 있는 모든 위치를 다음 레벨의 큐에 넣습니다.

 

Time 4에서 16에서 +1 연산을 통해 동생의 위치인 17에 도달하게 되어 최단 시간인 4초를 구할 수 있습니다.

 

이 때 중복을 피하기 위해서 방문 여부를 체크할 visited 배열을 사용하여 방문한 노드를 체크해줍니다. 위 예제에서는 노드4 에서 이동이 가능한 위치는 (3,5,8)인데, 5는 이미 시작노드에서 이미 방문했으므로 제외가 되는 것입니다.

---

전체 코드