문제 링크
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
문제 해설
Idea
- BFS
- N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색
- 두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행하고 K에 대한 거리를 출력
- N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단축을 위해 예외로 처리
Time Complexity
- O(N) = 100,000
Data Size
- N: 0 <= int <= 100,000
- K: 0 <= int <= 100,000
해설 코드
from collections import deque
def bfs(start, target):
MAX = 10**5
count = [0] * (MAX+1)
queue = deque([start])
while queue:
x = queue.popleft()
if x == target:
return count[x]
for nx in (x-1,x+1,x*2):
if 0 <= nx <= MAX and not count[nx]:
count[nx] = count[x] + 1
queue.append(nx)
N, K = map(int, input().split())
if N >= K:
print(N - K)
else:
print(bfs(N, K))
'Tech > Algorithm' 카테고리의 다른 글
[프로그래머스]n^2 배열 자르기 (Python) (0) | 2022.08.16 |
---|---|
[프로그래머스]n진수 게임 (Python) (0) | 2022.08.16 |
[백준 1676] 팩토리얼 0의 개수 (Python) (0) | 2022.08.16 |
[백준 1541] 잃어버린 괄호 (Python) (0) | 2022.08.16 |
[백준 1389] 케빈 베이컨의 6단계 법칙 (Python) (0) | 2022.08.16 |