[백준/파이썬] 1697번: 숨바꼭질

문제

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

풀이

• 동생을 찾을 수 있는 가장 빠른 시간
• 수빈이 위치 N(0 ≤ N ≤ 100,000)
• 동생 위치 K(0 ≤ K ≤ 100,000)
• 이동 방식
  1. X - 1
  2. X + 1
  3. 2 * X

최단 시간을 찾는 문제이므로 BFS를 활용해 문제를 풀면 됩니다.

최대 좌표가 100,000인걸 이용해 visited 배열을 생성해줍니다.

MAX = 100000
visited = [-1] * (MAX + 1)

조건들을 이용해 함수를 선언

def bfs():
	queue = deque([n]) # 시작(수빈이) 위치
    visited[n] = 0 # 시작 위치의 시간 0초로 초기화
    
    while queue:
    	x = queue.popleft()
        
        # 동생의 위치에 도착하면 종료
        if x == k:
	        return visited[x]

반복문을 이용해 이동할 수 있는 방식 탐색

        for nx in (x-1,x+1,x*2): # 앞, 뒤, 순간이동
            if 0 <= nx <= MAX and visited[nx] == -1: # 범위 내 && 미방문
                queue.append(nx)
                visited[nx] = visited[x] + 1 # 이전 시간 + 1

코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    queue = deque([n])
    visited[n] = 0

    while queue:
        x = queue.popleft()
        if x == k:
            return visited[x]
        
        for nx in (x-1,x+1,x*2):
            if 0 <= nx <= MAX and visited[nx] == -1:
                queue.append(nx)
                visited[nx] = visited[x] + 1

if __name__ == "__main__":
    n,k = map(int,input().split())
    MAX = 100000
    visited = [-1] * (MAX+1)

    print(bfs())