백준 1697 숨바꼭질 Python 3

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

1697번: 숨바꼭질

 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1697.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque
def find_sis(N, K):
    q = deque([[N, 0]])
    visit = [0]*100001
    visit[N] = 1
    while q:
        loc, sec = q.popleft()
        if loc == K:
            print(sec)
            return
        if 0 <= loc-1 and not visit[loc-1]:
            visit[loc-1] = 1
            q.append([loc-1, sec+1])
        if loc+1 <= 100000 and not visit[loc+1]:
            visit[loc+1] = 1
            q.append([loc+1, sec+1])
        if 0 <= loc*2 <= 100000 and not visit[loc*2]:
            visit[loc*2] = 1
            q.append([loc*2, sec+1])

input = sys.stdin.readline
N, K = map(int, input().split())
find_sis(N, K)

---

풀이 과정

풀이 시간 13분

import sys
from collections import deque
def find_sis(N, K):
    q = deque([[N, 0]])
    visit = [0]*100001
    visit[N] = 1
    while q:
    	#현재 수빈의 위치와 시간
        loc, sec = q.popleft()
        
        #동생을 찾은 경우, 숨바꼭질 종료
        if loc == K:
            print(sec)
            return
            
        #걸어서 이동
        if 0 <= loc-1 and not visit[loc-1]:
            visit[loc-1] = 1
            q.append([loc-1, sec+1])
        if loc+1 <= 100000 and not visit[loc+1]:
            visit[loc+1] = 1
            q.append([loc+1, sec+1])
            
        #순간 이동
        if 0 <= loc*2 <= 100000 and not visit[loc*2]:
            visit[loc*2] = 1
            q.append([loc*2, sec+1])

input = sys.stdin.readline
N, K = map(int, input().split())
find_sis(N, K)

#시간복잡도 = O(V+E), 공간복잡도 = O(n)