[백준 13549번] | 숨바꼭질 3 | BFS (파이썬)

문제 소개

수빈이와 수빈이 동생의 위치가 주어지고, 최소 시간 내 수빈이가 동생을 찾아야 하는 문제다

수빈이는 아래와 같이 세 가지 방법으로 이동할 수 있다

1. x - 1(1초)

2. x + 1(1초)

3. x * 2(0초)

수빈이의 위치 N, 동생의 위치 K 가 주어지며 수빈이가 K로 이동하는 최단시간을 구하는 것이다

문제 풀이 접근방식

최단경로를 구할때 유용한 BFS(너비 우선 탐색)을 사용하여 이동하면서 이동가능 위치의 최단방문시간을 갱신해보자

큐를 이용하여 방문

큐에 현재위치를 저장하여 큐에서 하나씩 꺼내 가능한 이동을 진행한다

dist[i](i에 도달하는 최소시간 배열)을 따로 두어 이동을 진행할때 최소 시간이면 방문하고 갱신한다

 

백준 문제

13549번: 숨바꼭질 3

백준 13549번

 

import sys
from collections import deque

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

# 최소 시간을 기록
dist = [float('inf')] * (MAX + 1)
dist[N] = 0  # 시작 위치는 0초

queue = deque([N])  # 큐에는 위치만

while queue:
    pos = queue.popleft()

    # 순간이동 (0초 소모)
    if pos * 2 <= MAX and dist[pos] < dist[pos * 2]:
        dist[pos * 2] = dist[pos]  # 갱신
        queue.appendleft(pos * 2)  # 0초 연산 우선

    # +1 이동 (1초 소모)
    if pos + 1 <= MAX and dist[pos] + 1 < dist[pos + 1]:
        dist[pos + 1] = dist[pos] + 1  # 갱신
        queue.append(pos + 1)  # 뒤에 넣음

    # -1 이동 (1초 소모)
    if pos - 1 >= 0 and dist[pos] + 1 < dist[pos - 1]:
        dist[pos - 1] = dist[pos] + 1  # 갱신
        queue.append(pos - 1)  # 뒤에 넣음

sys.stdout.write(f"{dist[K]}\n")

 

dist[N] - 위치 N까지의 최단시간

queue - 위치를 저장하며 bfs를 진행, 큐에서 꺼낸 위치에서 가능한 이동을 계산하여 최소 시간을 갱신한다

bfs 탐색 - x * 2, x - 1, x + 1로 이동한다. x * 2는 0초 이므로 우선 탐색, dist를 조회해서 최단시간이면 갱신 + 큐에 삽입

dist[K] - K까지의 최단시간

 

시간복잡도는 O(MAX)

 

정답

 

처음에는 K까지의 거리가 나오면 바로 출력하는 방식으로 작성을 했는데

K까지 가는방법이 여러개 있기때문에 이 방식으로는 반례가 존재할수도 있겠다는 생각이 들었다

처음 작성한 코드

import sys
from collections import deque
N, K = map(int,sys.stdin.readline().split())
MAX = 100000

queue = deque([(N,0)]) # 현재 수빈이 위치, 경과 시간
visited = set([N]) # 중복 방문 방지

while queue:
    pos, time = queue.popleft()

    if pos == K:
        sys.stdout.write(f"{time}\n")
        break
    if pos * 2 <= MAX and pos * 2 not in visited:
        visited.add(pos*2)
        queue.appendleft((pos * 2, time))
    if pos - 1 >= 0 and pos - 1 not in visited:
        visited.add(pos-1)
        queue.append((pos-1, time + 1)) # x - 1
    if pos + 1 <= MAX and pos+1 not in visited:
        visited.add(pos+1)
        queue.append((pos+1, time +1)) # x + 1

 

pos - 1 을 먼저고려한 이 코드는 정답으로 처리가 되었지만

pos + 1과 pos - 1의 위치를 바꾸면(pos + 1을 우선 고려하면) 99%에서 틀렸습니다가 나온다

 

반례

N = 4, K = 6

큐 추적

x+1을 먼저 고려 - (4,0)(8,0)(16,0)...(5,1)(3,1)(9,1)(7,1)(17,1)(15,1)...(6,2)
x-1을 먼저 고려 - (4,0)(8,0)(16,0)...(3,1)(5,1)(7,1)(9,1)(15,1)(17,1)...(6,1) 

 

위 코드로 정답처리 된 후 고려 순서에 따라 결과가 달라지는게 찝찝해서 다른 방식으로 풀어봤다

dp로도 풀 수 있을거 같은데 시간날때 해봐야겠다