[백준] 1697번 숨바꼭질 : 파이썬(python) 설명

 

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

1697번: 숨바꼭질

Hint

x

 

Solution

 

from collections import deque
n,k = map(int,input().split())

visit_list=[0]*100001 # 중복 제외
count_list=[1]*100001 # 거리

def bfs(v, end):
    q=deque()
    q.append(v)
    while q:
        v=q.popleft()
        if v==end:
            return True
        if 0<= v-1 <= 100000 and visit_list[v-1]==0:
            q.append(v-1)
            visit_list[v-1]=1
            count_list[v-1]+=count_list[v]
        if 0<= v+1 <= 100000 and visit_list[v+1]==0:
            q.append(v+1)
            visit_list[v+1]=1
            count_list[v+1]+=count_list[v]
        if 0<= v*2 <= 100000 and visit_list[v*2]==0:
            q.append(v*2)
            visit_list[v*2]=1
            count_list[v*2]+=count_list[v]

bfs(n,k)
print(count_list[k]-1) # 목적지까지 몇 초 걸렸는지

기본적인 너비 우선 탐색 알고리즘

 

유사 문제 : 2644번 촌수 계산

해당 문제와 문제 해결 방식이 비슷

노드 이동 횟수를 파악하는 사고 방식

 

visit_list: 이미 방문한 좌표를

다시 방문하지 않기 위한 함수

 

count_list: 해당 좌표에 도달하기 전까지

몇 번의 좌표를 이동했는지 계산하기 위한 함수