3월 30일 백준 특강
주어진 문제들은 여기(SWEA 사이트 맞습니다)에서 볼 수 있습니다.
1) BFS - 숨바꼭질 5
위의 링크에서 문제 설명을 꼭 읽어보세요!
EX) 수빈의 위치(N) : 17 , 동생의 위치(K) = 5
| 시간 | 동생 | 수빈 |
|---|---|---|
| 0 | 5 | 17 |
| 1 | 6 | 16,18,34 |
| 2 | 8 | 15,17,19,32,36,33,35,68 |
| 3 | 11 | 14,16,18,20 등등.. |
| 4 | 15 | 13,15,17,19,21 등등.. |
위의 예시로는 동생과 수빈이 최초로 만나는 시간은 4초입니다.
이 문제는 BFS로 접근하는게 좋습니다.
-
최단거리를 구해야 하며,
-
위치 X에서 가능한 다음 위치는 X+1, X-1, 2*X
3가지로 정해져 있기 때문입니다.
그런데 주의할 점이 있습니다.
일반적으로 bfs를 할 때는, 이전에 15를 방문했으면 visited[15] = True처럼 방문 처리해줘서 더이상 방문하지 않게끔 해줬는데,
이 경우에는, 이전에 방문했던 점들을 다시 방문해도 된다는 것이 특징입니다.
해결방법 1.
그러면 시간 T에 따라서 경우의 수가 3^T로, 기하급수적으로 증가하는게 아니냐고 생각할 수도 있지만
사실 그렇지는 않습니다. 같은 시간 T에서의 수빈의 위치가 겹치지 않게끔만 해준다면 가능한 수빈의 위치는 0~500000이기 때문에 50만(+1)개를 넘지 않을 것입니다.
아래는 그 방법을 구현한 코드입니다.
시간 T에 따라서 visited 배열의 값을 갱신해주기만 하면 됩니다.
from collections import deque
MAX_NUM = 500000
N, K = map(int, input().split())
visited = [-1 for _ in range(MAX_NUM+1)]
def bfs():
q = deque()
q.append((N, 0, K))
while len(q):
n, cnt, k = q.popleft()
if n == k:
return cnt
else:
for next_n in [n+1, n-1, 2*n]:
if 0 <= next_n <= MAX_NUM and visited[next_n] != cnt:
visited[next_n] = cnt
q.append((next_n, cnt+1, k+cnt+1))
if K > MAX_NUM:
return -1
res = bfs()
print(res)
이제 이 방식의 시간복잡도를 구하도록 하겠습니다.
- 시간마다 가능한 경우의 수 < 500000
- 가능한 시간 < sqrt(500000)
=> 총 시간 복잡도 : 500000*sqrt(500000) ~= 3억 5천만
왜냐하면, 동생이 0에서부터 시작했다고 가정해 봅시다.
| 시간 | 동생 |
|---|---|
| 1 | 1 |
| 2 | 1+2 |
| 3 | 1+2+3 |
| … | |
| T | 1+2+….+(T-1)+T |
가 되는데, 이 합은 고등학교때 배운 공식을 이용하면 (T+1) * T / 2가 되기 때문입니다.
동생의 위치 역시 50만을 넘으면 안되므로 최대 가능한 시간 T는 대략 50만의 (1/2)제곱꼴이 되는 것입니다.
1억에 1초라는 주먹구구식 공식을 적용해보면 대략 3초 정도 걸릴 것이라 예상이 가능한데,
슬프게도 주어진 시간은 0.25초밖에 안됩니다…. 네 시간초과 났습니다.
해결방법 2.
아까 예시를 다시 들고와 보겠습니다.
| 시간 | 동생 | 수빈 |
|---|---|---|
| 0 | 5 | 17 |
| 1 | 6 | 16,18,34 |
| 2 | 8 | 15,17,19,32,36,33,35,68 |
| 3 | 11 | 14,16,18,20 등등.. |
| 4 | 15 | 13,15,17,19,21 등등.. |
수빈은 2초에 15를 방문했다가, 4초에 15를 다시 방문합니다.
문제는 15뿐만 아니라 16, 17, 18, 19 등의 모든 위치들도 최초로 방문했던 시간에서 2초 뒤에 다시 재방문하는 모습을 볼 수 있습니다.
사실 당연합니다. 위치 X에서 +1과 -1을 번갈아서 하면 똑같은 위치가 되기 때문입니다.
즉, 2초에 15를 방문했다면, 4초, 6초, 8초… 등등 모든 2이상의 짝수시간에는 15를 방문할 게 뻔하다는 점입니다.
반대로 11초에 15를 방문했다면, 13초, 15초, 17초.. 등등 모든 11이상의 홀수시간에도 15를 방문하게 됩니다.
따라서 주어진 T초에 위치 15를 방문했는지를 알기 위해서는
위치 15를 방문한 짝수 최소시간과 홀수 최소시간만 알고 있으면 됩니다.
이를 이용해서 BFS를 새로 짜봅시다.
from collections import deque
MAX_NUM = 500000
N, K = map(int, input().split())
# visited[n][0] : 짝수 시간에 위치 n을 방문한 최소시간
# visited[n][1] : 홀수 시간에 위치 n을 방문한 최소시간
visited = [[-1 for _ in range(MAX_NUM + 1)] for _ in range(2)]
def bfs():
q = deque()
q.append((N, 0))
visited[0][N] = 0
while len(q):
n, cnt = q.popleft()
# flag : cnt가 홀짝인지 결정
flag = cnt % 2
for next_n in [n + 1, n - 1, 2 * n]:
if 0 <= next_n <= MAX_NUM and visited[1-flag][next_n] == -1:
# next_n 위치에는 cnt+1 시간에 방문할 것이니까.
# 그런데 cnt+1 시간은 홀짝이 바뀌므로 1-flag로 해줌.
visited[1-flag][next_n] = cnt+1
q.append((next_n, cnt+1))
# BFS : 먼저 가능한 모든 점을 방문하기.
bfs()
# 방문한 다음에 K를 늘려보면서 이 점에 방문할 수 있는지 확인하기.
t = 0
flag = 0
res = -1
while K <= 500000:
if visited[flag][K] != -1:
if visited[flag][K] <= t:
res = t
break
flag = 1 - flag
t += 1
K += t
print(res)
위 방식은 O(MAX_NUM) 의 시간복잡도가 소요됩니다.
왜냐하면 0 ~ MAX_NUM사이의 위치에 대해 홀수 최소시간과 짝수 최소시간
단 두개만 기록하면 더이상 재방문하지 않기 때문입니다.
