[python] 백준 1697번 숨바꼭질

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

1697번: 숨바꼭질

 

 

 

 

 

 

💻 코드

 

from collections import deque


def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()  # 시작점
        if x == k:
            print(visited[x])
            break
        for i in (x - 1, x + 1, x * 2):
            if 0 <= i <= MAX and not visited[i]:
                visited[i] = visited[x] + 1
                queue.append(i)


MAX = 10 ** 5
visited = [0] * (MAX + 1)  # 이동하는 거리 표현
n, k = map(int, input().split())

bfs()

 

 

📝 풀이

 

이 문제는 여러 경우의 수에서 최단 시간을 찾아야하는 문제로 BFS 관련 문제이다. 

수빈이가 동생한테까지 가는데 수빈이가 한 번에 이동할 수 있는 거리는 x - 1, x + 1, x * 2가 있고 이를 그래프로 만들어 BFS 알고리즘을 통해 해결할 수 있다.

일단 BFS는 큐 자료 구조를 이용하므로 deque를 import하여 deque 리스트를 만들어 준다. x를 시작점으로 두고 x가 k와 같아질 때까지 반복하도록 한다. 그리고 이동하는 거리를 표현하기 위한 0으로 이루어진 리스트 visited를 만들어준 것을 이용하여 그래프의 깊이가 1씩 커질 때마다 visited리스트의 해당 인덱스도 따라서 커지도록 만들어주면서 계속 반복하다보면 n과 k가 같아지게 되고 이를 출력하면 최단 시간이 나오게 된다. 

 

 

코드 이해

 

n = 5, k = 17일 때,

 

<bfs 함수>

 

deque 리스트 queue가 만들어주고 queue에 5를 추가 -> queue = [5]

queue 리스트가 비어있지 않으므로 실행

x에 5 대입 -> 시작점

5 != 17이므로 if문은 건너뛰고 아래의 for문 실행

i는 각각 4, 6, 10이 됨

0 <= 4, 6, 10 <= MAX이 성립하고 visited[4], visited[6], visited[10]이 모두 0으로 False, not visited[0]는 True가 되므로 if문이 성립하게 되어 if문 4, 6, 10 순서대로 실행

i == 4 일 때 visited[4] = visited[5] + 1

visited[5]는 0이므로 visited[4] = 1이 됨

i == 6, 10일 때도 마찬가지 visited[6] = 1, visited[10] = 1

queue 리스트에 4, 6, 10 추가 queue = [4, 6, 10]

---

다시 돌아가서 queue가 비어있지 않으므로 while문 실행

queue 리스트에서 가장 왼쪽에 있는 값(가장 먼저 들어간 값) 4를 x에 대입

 

반복...

---

visited[17] = visited[18] + 1

17을 queue에 추가한 후 queue 리스트에서 popleft한 것이 17일 때 x == k가 만족하므로 4 출력