최단 경로 스터디 자료를 만들다가 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 처럼 뒤에 넣어서 나중에 처리하도록 하는 최적화 기법이었다.
하지만 이 문제 기준으로는 이 최적화가 정답에 영향을 주는 요소는 아니었다.
'알고리즘 문제 > BOJ (Python3, C++)' 카테고리의 다른 글
[백준] 19663 - Mountains (0) | 2024.07.26 |
---|---|
[백준] 11003 - 최솟값 찾기 (Python, 우선순위 큐) (0) | 2024.07.23 |
[백준] 1600 - 말이 되고픈 원숭이 (Python) (2) | 2024.07.14 |
[백준] 11780 - 플로이드 2 (Python) (2) | 2024.07.07 |
[백준] 21606 - 아침 산책 (Python) (2) | 2024.07.05 |