[Python] 백준 13549: 숨바꼭질 3 (이걸 그래프로 이해한다고?)

🔗 문제 링크

13549번: 숨바꼭질 3

💊 문제 요약

수빈이는 숨바꼭질 중이다. 자신은 N, 동생은 K에 위치하고 있는 것을 알게 되었다. 수빈이의 위치가 X일 때 걷는다면 1초 뒤에, X+1, X-1로 이동한다. 또는, 순간이동하여 0초 후에 2*X로 이동할 수 있다. 수빈이가 동생에게 가장 빠르게 가는 시간을 구하시오.

🌿 풀이 설명

그리디 문제로 해결하려 했지만, 틀렸습니다 로 인해 문제 유형을 확인하였다.

그래프 이론, 특히 너비 우선 탐색을 사용하여 풀어야 한다는 것을 확인하였다.

응 근데 그래프.? 🫤

내가 알던 그래프는

이런 건데... 지금 문제의 상태는 [{현재 위치}, {시간}] 이면 간선의 가중치를 어떻게 정의해야 하지?

숨바꼭질 3은 간선의 가중치가 변할 수 있는 그래프로 문제를 해석하여 푸는 것이 핵심이었다. 

 

1. 첫 번째 시도: 그리디 알고리즘 (틀렸습니다.)

문제 입출력 예시로,

입력: 5 17

출력: 2

가 있었는데, 17에서 ① 홀수면, +1 또는 -1 후에 2로 나눈다. ② 짝수면, 바로 2로 나눈다. 를 반복했을 때에도 같은 출력값을 가지는 것을 발견했다. 입력이 '4 17', '6 17'에서도 정답이 나오는 것을 확인하고 답안을 작성하였다.

 

1회 오답 후, 질문 게시판에서 반례 모음을 확인하였고, '0 K' 형태의 답안에서 프로그램이 종료되지 않는 예외가 있어 이 경우 예외 처리까지 하였으나, 오답 판정되었다. 

그리디로 시도했던 풀이 (틀렸습니다)

from collections import deque
N, K=map(int, input().split())

min_time=1000001
if N==0 and K!=0:
    N=1
    nxt=deque([(K, 1)])
else:
    nxt=deque([(K, 0)])

while nxt:
    x, time=nxt.popleft()
    if x<=N:
        min_time=min(min_time, time+(N-x))
        continue
    if x%2==0:
        nxt.append((x//2, time))
    elif x%2==1:
        nxt.append(((x+1)//2, time+1))
        nxt.append(((x-1)//2, time+1))

print(min_time)

2. 두 번째 시도: BFS를 사용한 풀이

BFS로 문제를 풀 때, 주의해야 할 점은 다음과 같다.

※ 일반적인 정의와 다른 포인트: visited를 방문 여부를 담은 list가 아니라, BFS에서 해당 노드를 방문할지 결정하는 정보 list라고 생각하자. 

 

① visited를 사용하지 않으면 X+1과 X-1을 무한으로 왔다갔다하며 프로그램이 종료되지 않는다. 따라서 사용하여야 한다.

 

② visited에 min_time을 저장하여, 해당 min_time보다 작은 경우 노드에 방문하도록 설정하여야 한다. 방문 노드의 순서를 queue로 관리하는데, 다익스트라 알고리즘에서 최단 거리를 보장하려면 각 노드별 가장 작은 가중치를 가진 노드를 먼저 탐색하여야 한다. 하지만, 코드가 time 순이 아니라 걷기 또는 순간이동의 횟수의 증가 순으로 append되므로 이 조건을 만족하지 않는다.

 

정답 풀이

from collections import deque
N, K=map(int, input().split())

nxt=deque([(N, 0)])
visited=[1000001 for _ in range(100001)]
min_time=1000001
while nxt:
    x, time=nxt.popleft()
    if x<0 or x>100000:
        continue
    if visited[x]>time:
        visited[x]=time
    elif visited[x]<=time:
        continue

    if x>=K:
        min_time=min(time+x-K, min_time)
        continue

    nxt.append((2*x, time))
    nxt.append((x+1, time+1))
    nxt.append((x-1, time+1))
    
print(min_time)

문제를 그래프로 이해한다는 것에 대한 시야가 커진 기분이다 👍