1697 숨바꼭질 (python)

문제

 

알고리즘

BFS 탐색을 사용해 풀 수 있다.

코드

import sys

from collections import deque

def bfs(v):

    q = deque([v]) # 시작점 v를 q에 추가

    while q:

        v = q.popleft() # 덱의 왼쪽에서 요소 제거하고 반환

        if v == k: # 현 위치가 동생과 같을 때

            return array[v]

        # 다음 위치로 이동할 수 있는 경우의 수 확인

        for next_v in (v-1, v+1, 2*v):

            # 위치가 범위 내에 있고, 아직 방문하지 않은 위치라면

            if 0 <= next_v < MAX and not array[next_v]:

                array[next_v] = array[v] + 1 # 다음 위치까지 시간 기록

                q.append(next_v) # 다음 위치를 q에 추가

MAX = 100001

n, k = map(int, sys.stdin.readline().split())

array = [0] * MAX

print(bfs(n))

 

코드 설명

BFS 과정 설명

 

for next_v in (v-1, v+1, 2*v)

이동 가능한 범위인 v-1, v+1, 2*v를 탐색

 

if 0 <= next_v < MAX and not array[next_v]

not array[next_v]가 방문하지 않은 위치라는 것을 알아낼 수 있는 이유는

처음에 array를 0으로 초기화 해뒀고, 0(False)이 아닌 값이라면 이미 방문했던 위치기 때문에

방문하지 않은 위치라면 not 0(False) == True가 되어 if문이 실행된다.

 

array[next_v] = array[v] + 1

방문하지 않은 위치를 BFS로 탐색을 했다면, array[next_v] 값을 그 전 시간에서 +1 시킨다.

 

q.append(next_v) 

다음 위치를 q에 추가한다.

 

 

예제 입력 1처럼 5 17이 입력으로 들어온다면

수빈이의 위치 5, 동생의 위치 17

 

next_v로 BFS탐색을 하며, 시간인 array[next_v]값을 1초씩 늘려간다.

 

늘려가며 탐색하다가 v == k, 즉 수빈이의 위치와 동생의 위치가 같다면

array[v]를 출력한다.