• 백준 12851 숨바꼭질2 : https://www.acmicpc.net/problem/18511

1. 문제설명

• N에서 출발해서 K까지 도달하는 데 걸리는 최단 거리 & 최단 거리로 갈 수 있는 방법이 몇 개인지
• 이동 가능 방법 : -1 , +1, *2
• 예) 그림 추가 예정

2. 접근 방식

• 이동 가능 방법인 -1, +1, *2를 반복문으로 돌면서 K에 도달할 때까지 BFS 돌리기
• isFind를 사용해 최단거리를 찾기 전/후로 분기처리 함
  • 찾기 전(false)에는 BFS 돌리고
  • 찾은 후(true)에는 K일 때 cnt++ 하도록

3. 틀린 이유 설명

• 기존 방식의 BFS를 사용하면 최단거리는 구할 수 있지만, 최단 거리로 갈 수 있는 모든 경우를 세지는 못함

  ( ∵ 기본 BFS는 한 번 사용한 숫자를 중복 처리해서 없애 버리기 때문 )

• 예) 5에서 출발했을 때

  1층 (4, 6, 10)
  2층 (3, 8, 7, 12, 9, 11, 20)
  3층 (2, 16, 14, 13, 24, 18, 22, 19, 21, 40)
  4층 (1, **15**, 17, 32, **✓15✓**, 28, 26, **23**, 25, 48, 36, **✓23✓**, 44, 38, 42, 39, 41, 80)
  // 기존의 BFS 방법을 사용하면 중복이 제거된 채 queue에 들어감
  1 **15** 17 32 **✓✓** 28 26 **23** 25 48 36 **✓✓** 44 38 42 39 41
  

• 즉, 같은 층위에서 중복되는 수는 살려야 한다.