📑 문제
문제링크 : 숨바꼭질 5
🤔 생각의 흐름
방문한 칸에 다시 방문하지 않아도 되는 BFS 문제로 생각했습니다. 그런데 N = 3, K = 0 인 경우, K가 0 → 1 → 3 으로 변할 때, N이 3 → 2 → 3 이어야 최소가 됩니다. 경우에 따라 방문한 위치에 재방문해야하는 경우가 있더라구요.
그런데 방문한 위치에 다시 가려면 2초가 필요합니다. N + 1 혹은 N - 1 로 갔다가 다시 N 으로 와야하니까요. 그래서 방문한 위치에 대한 기록을 짝수 초가 지났을 때와 홀수 초가 지났을 때, 2가지 경우로 나누어 생각해야 한다고 생각했습니다.
홀수 초가 지났는데 이미 N 이 홀수 초에 방문했던 곳이라면, N 은 N + 1 이나 N - 1 로 갔다가 N 으로 돌아오는 행동을 계속 방문하면서 기다리고 있으면 만날 수 있게되므로, 그 때의 BFS 단계가 답이 됩니다.
🎯 풀이방법
BFS 문제이며, 시간복잡도는 $O(500,000)$ 입니다.
visited[i][j] : i = 0 인 경우 짝수초, i = 1 인 경우 홀수초. 위치 j 에 도착했을 때의 BFS 단계를 저장한 리스트
맨 처음에 N == K 라면 0 을 return 합니다.
초기위치 N을 큐에 넣고 K <= 500,000 인 동안 BFS 를 진행합니다.
큐에 저장되어 있는 위치 pos 로부터, pos - 1, pos + 1, 2 * pos 가 구간 [0, 500,000] 에 있는지 확인하고, 구간 안에 있다면 visited 리스트를 이용하여 이전에 현재와 같은 홀/짝 초에 방문한적 있는지 확인합니다.
방문한적 없다면 큐에 해당 위치를 넣어주고 visited 에 기록합니다.
K 위치에 현재의 홀/짝 초에 N 이 방문한적 있는지 확인하고, 방문한적 있다면 현재의 BFS 단계를 return 합니다. 방문한 적이 없다면 K 를 조건에 맞게 이동시켜주고 다음 BFS 단계를 수행합니다.
K <= 500,000 인 동안 만날 수 없었다면 -1 을 return 해줍니다.
🔎 유의할 점
- 이 문제는 방문한 위치에 다시 방문할 수 있습니다. 하지만 다시 방문하기 위해서는 2초가 필요하므로, 짝수초와 홀수초로 나누어서 풀어야 합니다.
💻 코드
가독성이 좋은 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from sys import stdin
input = stdin.readline
def solve():
N, K = map(int, input().split())
if N == K:
return 0
visited = [[0] * 500_001 for _ in range(2)]
que = [N]
K += 1
ans, i = 1, 2
while K <= 500_000:
new_que = []
is_odd = i & 1
for pos in que:
for p in [pos - 1, pos + 1, 2 * pos]:
if 0 <= p <= 500_000 and not visited[is_odd][p]:
visited[is_odd][p] = ans
new_que.append(p)
que = new_que
if visited[is_odd][K]:
return ans
ans += 1
K += i
i += 1
return -1
if __name__ == '__main__':
print(solve())
조금 더 빠른 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from sys import stdin
input = stdin.readline
def solve():
N, K = map(int, input().split())
if N == K:
return 0
ans = 1
visited = [[0] * 500_001 for _ in range(2)]
que = [N]
i = 2
K += 1
while K <= 500_000:
new_que = []
is_odd = i & 1
for pos in que:
# pos - 1
p = pos - 1
if 0 <= p and not visited[is_odd][p]:
visited[is_odd][p] = ans
new_que.append(p)
# 2 * pos <= max_pos 인 경우, pos + 1 <= max_pos 이다
p = 2 * pos
if p <= 500_000:
# 2 * pos
if not visited[is_odd][p]:
visited[is_odd][p] = ans
new_que.append(p)
# pos + 1
p = pos + 1
if not visited[is_odd][p]:
visited[is_odd][p] = ans
new_que.append(p)
# pos + 1
elif pos < 500_000 and not visited[is_odd][pos + 1]:
p = pos + 1
visited[is_odd][p] = ans
new_que.append(p)
que = new_que
if visited[is_odd][K]:
return ans
ans += 1
K += i
i += 1
return -1
if __name__ == '__main__':
print(solve())
Comments powered by Disqus.