https://www.acmicpc.net/problem/1697
BFS(너비 우선 탐색)을 사용하여 수빈이가 동생을 찾는 최소 시간을 구하는 문제
from collections import deque
def bfs(start, target):
# 최대 범위 설정 (문제 조건에서 수빈이와 동생의 위치는 0 이상 100000 이하)
max_range = 100000
# 방문 여부 및 시간을 저장하는 리스트
visited = [0] * (max_range + 1)
queue = deque([start])
while queue:
current = queue.popleft() # 큐에서 현재 위치를 꺼냄
if current == target:
return visited[current] # 동생을 찾으면 소요된 시간 반환
# 현재 위치에서 갈 수 있는 세 가지 경우를 탐색
for next_pos in (current - 1, current + 1, current * 2):
if 0 <= next_pos <= max_range and not visited[next_pos]:
visited[next_pos] = visited[current] + 1 # 방문 시간 갱신
queue.append(next_pos) # 큐에 다음 위치 추가
def main():
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0]) # 수빈이의 위치
k = int(data[1]) # 동생의 위치
result = bfs(n, k) # BFS를 통해 최소 시간을 계산
print(result) # 결과 출력
if __name__ == "__main__":
main()
'Algorithm > 백준' 카테고리의 다른 글
백준 코딩테스트 1543 문서 검색 (0) | 2024.08.06 |
---|---|
항해99 리부트코스 알고리즘 2주 5일차 백준 10815 숫자 카드 (0) | 2024.07.29 |
항해99 리부트코스 알고리즘 2주 5일차 백준 2606 바이러스 (0) | 2024.07.29 |
항해99 리부트코스 알고리즘 2주 5일차 백준 18352 특정 거리의 도시 찾기 (0) | 2024.07.29 |
항해99 리부트코스 알고리즘 2주 5일차 백준 7562 나이트의 이동 (0) | 2024.07.29 |