[백준] 13549 - 숨바꼭질 3 (BFS 풀이)

최단 경로 스터디 자료를 만들다가 BFS로 최단 경로를 찾는 연습문제로 숨바꼭질이 생각나서 다시 풀어봤다.

그런데 단순하게 BFS로 풀릴 줄 알았는데 맞왜틀을 해서 충격을 받았다.. (심지어 과거의 나는 1트만에 풀었었다..)

 

과거에 풀었던 풀이는 우선순위 큐를 이용한 다익스트라 풀이였다.

이 풀이는 정말 다익스트라의 최단 경로 알고리즘을 곧이 곧대로 사용하는 것이니 틀릴 여지가 거의 없다.

 

그런데 BFS로 이 문제를 푸는 경우에는 여러가지를 고려해야 했다.

from collections import deque

n, k = map(int, input().split())
visit = [False] * 200001
d = deque()
d.append((n, 0))
visit[n] = True

while d:
    now, time = d.popleft()
    if now == k:
        print(time)
        exit()

    if now < 200000 and not visit[now+1]:
        d.append((now+1, time+1))
        visit[now+1] = True

    if now > 0 and not visit[now-1]:
        d.append((now-1, time+1))
        visit[now-1] = True
    
    if now <= 100000 and not visit[now*2]:
        d.append((now*2, time))
        visit[now*2] = True

 

 

이 코드는 내가 최초에 제출하고 틀렸던 코드이다.

이 코드가 틀린 이유는 바로 곱셈을 먼저 처리하지 않은 것이었다.

 

그냥 숨바꼭질 문제는 모든 선택이 동일하게 1초가 소요되어 순서가 중요하지 않았지만, 이 문제는 곱셈으로 순간이동 할 때는 시간이 들지 않아서 먼저 처리하는 것이 이득이다.

 

from collections import deque

n, k = map(int, input().split())
visit = [False] * 200001
d = deque()
d.append((n, 0))
visit[n] = True

while d:
    now, time = d.popleft()
    if now == k:
        print(time)
        exit()
    
    if now <= 100000 and not visit[now*2]:
        d.append((now*2, time))
        visit[now*2] = True

    if now < 200000 and not visit[now+1]:
        d.append((now+1, time+1))
        visit[now+1] = True

    if now > 0 and not visit[now-1]:
        d.append((now-1, time+1))
        visit[now-1] = True

 

그래서 이렇게 곱셈을 먼저 처리하도록 순서를 바꾸었다.

하지만 이렇게 푸니 99%에서 틀렸다 ㅠㅠ

 

아무리 생각해도 이유를 모르겠어서 질문게시판을 탐방하다가 곱셈 - 뺄셈 - 덧셈 순서로 처리해야 한다는 댓글을 발견했다.

그 이유는 덧셈 + 덧셈을 통해서 가는 것보다 뺄셈 - 곱셈을 통해서 가는 것이 더 빠를 수 있기 때문이라는 이유였다.

(직관적인 이유는, 뺄셈 + 곱셈을 통해 이동하는 것이 덧셈을 통해 이동하는 것보다 더 적은 이동 횟수를 사용하기 때문이라고도 생각할 수 있다.)

 

그래서 관련된 반례를 생각해봤다.

덧셈을 두번한 것과 뺄셈 후 곱셈을 했을 때 같은 값이 나오는 값이 무엇인지 한번 방정식을 풀어보았다.

 

x + 2 = (x-1) * 2

 

이 방정식을 풀면 x = 4 가 나온다.

따라서 4 6 을 입력으로 넣으면 왜 뺄셈을 먼저 해야 하는지 알 수 있다.

 

만약 덧셈을 먼저처리하고, 뺄셈을 다음으로 처리하는 경우, 큐에는 다음과 같은 순서로 데이터가 들어간다.

 

4

8 (곱셈 먼저 처리)

8 5 (덧셈을 다음으로 처리)

8 5 3 (뺄셈을 다음으로 처리)

 

따라서 8을 처리한 이후에 5가 나와서 1을 더한 순간 6이 나오므로 최단 경로를 2로 잡아버린다.

만약 뺄셈을 먼저 처리했다면 8 3 5 순으로 큐에 들어있으므로 3을 먼저 처리해서 최단 경로를 1로 잡을 수 있게 된다.

 

from collections import deque

n, k = map(int, input().split())
visit = [False] * 200001
d = deque()
d.append((n, 0))
visit[n] = True

while d:
    now, time = d.popleft()
    if now == k:
        print(time)
        exit()

    if now <= 100000 and not visit[now*2]:
        d.appendleft((now*2, time))
        visit[now*2] = True
        
    if now > 0 and not visit[now-1]:
        d.append((now-1, time+1))
        visit[now-1] = True

    if now < 200000 and not visit[now+1]:
        d.append((now+1, time+1))
        visit[now+1] = True

 

따라서 위와 같이 작성하는 것이 맞다.

 

추가로, 이 문제는 0-1 BFS 로도 분류되었다.

궁금해서 0-1 BFS를 찾아봤는데, 비용이 0인 경우에는 덱의 앞쪽에 넣어서 그 다음에 먼저 고려하도록 하고, 1일 때는 BFS 처럼 뒤에 넣어서 나중에 처리하도록 하는 최적화 기법이었다.

 

하지만 이 문제 기준으로는 이 최적화가 정답에 영향을 주는 요소는 아니었다.