[BFS,DFS] 백준 Sliver1 1697 숨바꼭질

문제

https://www.acmicpc.net/problem/1697

---

설계 ✨

1. 처음 수빈이의 위치 N 에서 동생의 위치 K로 가는 최단 시간을 찾는 것이다.
2. 최단 시간을 찾는 것이기에 DFS, BFS를 먼저 생각할 수 있다.
3. 기존 위치에서 이동하는 위치는 3가지 X - 1, X + 1, 2 x X 로 총 3가지가 있다. 즉 노드가 3개로 펼쳐져 나갈 수 있다.
4. 하나의 노드가 얼마나 깊이까지 가는지 모두 확인해서 최단시간을 찾으려면 모든 경로를 다 탐색해야하므로 비효율적이다. 즉 DFS 보다는 BFS 임을 생각한다.
5. BFS로 문제를 풀기로 했으니, 기존 BFS 코드를 작성한다.
6. 다음 노드로 펼쳐져 가는 것이 3가지가 있으니 Queue에 append할 아이템이 3가지이다.
7. X - 1, X + 1, 2 x X 값이 범위를 넘어가지 않도록 조건문을 사용해준다.
8. 방문 위치를 표시하기 위한 방법을 생각해 Array 하나를 만들어 준다.

 

 

다음은 참고한 블로그 링크입니다. 

핵심 자료구조 - 그래프 : 최단 경로 : ① : BFS, 다익스트라

[Python] 백준 1697번 숨바꼭질 - 차근차근 문제접근

 

---

import sys
from collections import deque

def bfs(v):
    q = deque([v]) # 큐 선언
    while q:
        v = q.popleft()
        if v == k: # 큐에서 꺼낸 노드가 k와 같을 때 (동생의 위치에 도착했을 때)
            return array[v] # 값 리턴
        for next_v in (v-1, v+1, 2*v): # -1만큼 이동, +1만큼 이동, *2만큼 순간이동할 수 있음
            if 0 <= next_v < MAX and not array[next_v]: # 범위 조건 and 방문하지 않았을 때
                # not array[i] -> array[i]가 0이면 실행
                array[next_v] = array[v] + 1 # 이동할 때마다 1초가 소요되므로 누적해서 시간 쌓기
                q.append(next_v) # queue에 이동한 위치 넣기



MAX = 100001 # 백준 범위
n, k = map(int,input().split())
array = [0] * MAX # 각 위치마다 몇 초 걸렸는지 담기 위한 리스트
print(bfs(n))