[BOJ:1697] 숨바꼭질

문제

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

문제해결방법

• 문제를 해결하는 방법은 0초일 때 수빈이의 위치 1초일 때 수빈이의 위치, 2초일 때 수빈이의 위치 ... n초 일때 수빈이의 위치와 동생의 위치를 비교하면서 두 위치가 값을 때의 가장 빠른 시간을 찾아야한다. 가장 빠른 시간을 찾을 것이기 때문에 시간마다 위치를 확인하고 아니라면 다음 1초후의 시간을 확인해야한다. 이때 활용하기 좋은 자료구조는 큐이다.
• N초 일때 위치를 확인하고 다시 그 때의 위치가 동생의 위치와 다르면 다시 그 위치로부터 1초 후 이동가능한 세가지 위치와 시간을 N+1을 하여 큐에 넣는다. 큐를 사용하는 이유는 큐는 먼저 들어간 값이 먼저 나오는 자료구조 인데 시간과 위치 값을 넣고 빼고를 반복하면서 자료를 다음 자료를 꺼낼 때 그 다음 1초후의 위치들을 꺼내야
• 0초 일때는 시작위치 이고, 그 다음 부터 1초일때 갈 수 있는 위치 X-1,X+1, X*2의 위치를 현재의 시간 값과 함께 큐에 넣는다.
• 큐에서 데이터를 꺼내고 꺼낸 데이터의 위치가 동생의 위치가 맞다면 꺼낸 데이터의 시간 값을 출력한다.

코드

import sys
from collections import deque

input = sys.stdin.readline

subin, brother = map(int, input().split())
visited = [False]*(100001)
q = deque()

q.append((subin,0))

while q:
    cur, time = q.popleft()

    if cur == brother:
        print(time)
        break

    for move in [-1,1,cur]:
        next = cur + move
        if 0<= next <= 100000 and not visited[next]:
            visited[next] = True
            q.append((next,time+1))