문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력 1
2
힌트
수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.
문제풀이
'''
백준 골드5
13549번
숨바꼭질3
'''
from collections import deque
n, k = map(int, input().split())
queue = deque([(n, 0)]) # (현재위치, 경과시간)
visited = [False] * 100001 # 방문하지 않은 노드 : false, 방문한 노드: true
visited[n] = True
while queue:
current, time = queue.popleft()
# 수빈이가 동생을 찾은 경우
if current == k:
print(time)
break
# 다음에 방문할 수 있는 노드의 경우의 수
next_positions = [current * 2, current - 1, current + 1]
for next_pos in next_positions:
if 0 <= next_pos < 100001 and not visited[next_pos]:
visited[next_pos] = True
# 순간이동을 하는 경우
if next_pos == current * 2:
queue.appendleft((next_pos, time))
# -1 또는 +1 로 이동하는 경우
else:
queue.append((next_pos, time + 1))
BFS를 이용해서 해결하였다. 사실 BFS 자체를 구현하는건 크게 어렵게 안 느껴지는데 이 문제를 BFS로 적용하자 라는 생각을 하기까지 너무 어려운 것 같다.
전에 코테 공부할 때도 그래프 관련 알고리즘이 제일 어려웠던 것 같은데,,, 한 번 다시 복습하는 시간을 가져봐야겠다.!
'코딩테스트 > 백준(Python)' 카테고리의 다른 글
[백준][Python] 20006번. 랭킹전 대기열 (실버2) (0) | 2024.07.11 |
---|---|
[백준][Python] 21921번. 블로그 (실버3) (0) | 2024.07.11 |
[백준][Python] 3758번. KCPC(실버2) (0) | 2024.07.07 |
[백준][Python] 20922번. 겹치는 건 싫어(실버1) (0) | 2024.07.06 |
[백준][Python] 15989번 1, 2, 3 더하기 4(골드5) (0) | 2024.07.06 |