Default
- 런타임에러 방지를 위해
sys.stdin 과 sys.stdout 을 이용한다.
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
1
2
3
| import sys
N, K = map(int, sys.stdin.readline().split())
|
BFS
- 이진 탐색 그래프에서 가장 얕은 깊이를 출력하면 됨 == BFS
1
2
3
4
5
| def bfs():
queue = [N]
while queue:
now = queue.pop(0)
|
now == K 일 때, 해당 깊이를 출력하면 됨
1
2
3
| if now == K:
sys.stdout.write(str(cnt[now]))
return
|
- 그래프를 그리며 경우의 수를 파악하였지만, 모든 경우에 대하여 bfs 하는 것을 생각하지 못함
- 주어진 범위에 따라 범위 내의 값인지 파악하고
- 한 단계 더 깊어질 경우
깊이 == 현재의 높이+1 이므로, cnt += 1 을 시행한다.
- 이를 위해 0으로 초기화된 범위 만큼의 배열을 생성한다.
1
2
3
4
| for next in (now-1, now+1, 2*now):
if 0 <= next <= 100000 and not cnt[next]:
queue.append(next)
cnt[next] = cnt[now]+1
|
Output
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
1
2
3
| if now == K:
sys.stdout.write(str(cnt[now]))
return
|