[백준] 1697번 숨바꼭질 파이썬 정답 풀이

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

---

1. 풀이

• BFS 알고리즘을 사용하자

문제에서 말하는 최소 시간은 결국 수빈이가 동생까지 가는 데 이동하는 최단 거리로 치환할 수 있다. 또한 앞으로 1칸 이동, 뒤로 1칸 이동, 순간 이동은 모두 이동하는 데 1초가 걸린다. 즉, 모든 이동 방식의 가중치가 모두 1이다. 따라서 이 문제는 가중치가 1로 동일한 그래프에서 최단 경로를 찾는 것이므로 BFS 알고리즘이 적합하다. 참고로 BFS는 노드를 한 번만 방문하면 되며, 처음으로 노드를 방문한 시점이 가장 빠른 시간임을 보장한다.

 

번외로 dp를 통해 문제를 해결할 수는 있지만, dp는 일반적으로 이동에 따른 가중치가 서로 다른 경우에 활용한다.

 

 

 

2. 정답 코드

from collections import deque


INF = 999999
n, k = map(int, input().split())

visited = [False] * 100001
times = [INF] * 100001
times[n] = 0
queue = deque([n])

while queue:
    x = queue.popleft()

    if x == k:
        break

    if x < 100000 and not visited[x + 1]:
        visited[x + 1] = True
        times[x + 1] = times[x] + 1
        queue.append(x + 1)
    
    if x > 0 and not visited[x - 1]:
        visited[x - 1] = True
        times[x - 1] = times[x] + 1
        queue.append(x - 1)
    
    if x * 2 <= 100000 and not visited[x * 2]:
        visited[x * 2] = True
        times[x * 2] = times[x] + 1
        queue.append(x * 2)
    
print(times[k])

 

 

 

백준에 코드를 제출하고나서 다른 사람들의 코드도 확인해 보았는데,

더 깔끔하고 간단하게 코드를 작성할 수 있어 추가로 기록한다.

 

from collections import deque


n, k = map(int, input().split())

visited = [False] * 100001
queue = deque([(n, 0)])

answer = -1
while queue:
    x, time = queue.popleft()

    if x == k:
        answer = time
        break

    for y in [x - 1, x + 1, x * 2]:
        if 0 <= y <= 100000 and not visited[y]:
            queue.append((y, time + 1))
            visited[y] = True

print(answer)