[BFS] 백준 #1697 숨바꼭질 - Python

🗂️ 문제

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

 

 

💡 접근법

maps라는 1차원 리스트를 선언하고, BFS를 통해 현재 위치에서 +1, -1, *2칸을 더한 위치를 탐색한다. 이때 방문 처리를 위한 visited라는 리스트는 따로 생성하지 않고, maps가 0인 경우 방문하지 않은 것으로 간주하여 처리한다.

 

또한, 위치의 범위(0 ≤ N ≤ 100,000)가 정해졌으므로, 이를 기준으로 리스트의 길이와 위치 범위를 벗어났을 때의 처리 조건을 미리 선언해 둔다. 만약 현재 위치가 수빈이의 위치(K)일 경우 조건문을 통해 탈출하고, 현재 위치의 값을 반환한다.

 

😎 (틀린) 내 코드

import sys
from collections import deque

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

maps = [0] * (100000+1)

move = [1, 1, 2]
cal = ["-", "+", "*"]

def BFS(v):
    queue = deque([v])

    while queue:
        n = queue.popleft()

        for m, c in zip(move, cal):
            expression = str(n) + c + str(m)
            x = eval(expression)
            if x >= 0 and x <= 100000 and maps[x] == 0:
                maps[x] = maps[n] + 1
                queue.append(x)

BFS(N)
print(maps[K])

해당 코드에서는 BFS가 실행되면서 큐가 빌 때까지 계속 실행되는데, 처음으로 K에 도달하는 경우가 최단 시간이다.

따라서 처음으로 K에 도달하면 그때의 maps[K] 값이 최단 시간임을 보장한다. 이후 큐에 있는 다른 상태를 탐색할 필요가 없으므로 즉시 종료하는 조건을 추가해야 한다.

 

👀 배운 코드

import sys
from collections import deque

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

maps = [0] * (100000+1)

move = [1, 1, 2]
cal = ["-", "+", "*"]

def BFS(v):
    queue = deque([v])

    while queue:
        n = queue.popleft()
        
        if n == K:
            return maps[K]
        for m, c in zip(move, cal):
            expression = str(n) + c + str(m)
            x = eval(expression)
            if x >= 0 and x <= 100000 and maps[x] == 0:
                maps[x] = maps[n] + 1
                queue.append(x)

print(BFS(N))

K에 도달한 순간 즉시 종료함으로써 최단 경로를 반환한다.

 

🧐 배운 점

• for i in (cur+1, cur-1, cur * 2):
  • +1칸, -1칸, *2칸을 계산하기 위해 eval() 함수를 사용했는데, 위와 같이 for 문 안에서 튜플로 값을 한 번에 정의해두고 사용할 수 있다.
• BFS는 최단 경로를 계산하는 데 최적화된 알고리즘이므로, 원하는 목적지에 제일 먼저 도달했을 때 바로 값을 출력해야 한다. 그렇지 않으면, 구해진 최단 경로의 값이 다른 경로에 의해 덮어씌워진다.

 

✅ 정답 확인