[python] 백준 5014번 스타트링크

백준 5014번 스타트링크

https://www.acmicpc.net/problem/5014

문제

풀이

이거슨 BFS 를 이용하는 문제. 최단 경로를 찾을 때이기 때문.

F: 건물의 층수
S: 현재 위치
G: 목표 위치
U: 위로 가는 층 수
D: 아래로 가는 층 수

count 를 데크에 넣을 때

from collections import deque

# 입력 받기
F, S, G, U, D = map(int, input().split())  # F: 건물의 층수, S: 현재 위치, G: 목표 위치, U: 위로 가는 층 수, D: 아래로 가는 층 수

queue = deque([(S, 0)])  # 시작 위치와 초기 버튼 누름 횟수를 튜플로 추가
visited = [False] * (F + 1)
visited[S] = True

def bfs(F, S, G, U, D):
    while queue:
        current, count = queue.popleft()
        if current == G:
            return count

        if current + U <= F and not visited[current + U]:
            visited[current + U] = True
            queue.append((current + U, count + 1))

        if current - D > 0 and not visited[current - D]:
            visited[current - D] = True
            queue.append((current - D, count + 1))

    return "use the stairs"

print(bfs(F, S, G, U, D))

count 를 데크에 넣지 않을 때

from collections import deque

# 입력 받기
F, S, G, U, D = map(int, input().split())  # F: 건물의 층수, S: 현재 위치, G: 목표 위치, U: 위로 가는 층 수, D: 아래로 가는 층 수

queue = deque([S])
visited = [False] * (F + 1)
visited[S] = True

def bfs(F, S, G, U, D):
    count = 0
    while queue:
        for _ in range(len(queue)):  # 현재 레벨의 모든 노드를 처리
            current = queue.popleft()
            if current == G:
                return count

            if current + U <= F and not visited[current + U]:
                visited[current + U] = True
                queue.append(current + U)

            if current - D > 0 and not visited[current - D]:
                visited[current - D] = True
                queue.append(current - D)
        
        count += 1  # 한 레벨의 탐색이 끝나면 count를 증가시킴

    return "use the stairs"  # 목표 층에 도달할 수 없는 경우

print(bfs(F, S, G, U, D))

📌 주의

• count 를 데크에 넣지 않을 때 for 문 까먹지 말기
• queue = deque() # 빈 deque를 생성
  queue.append((S, 0)) # (S, 0) 튜플을 deque에 추가
  는 다음과 같다:
  queue = deque([(S, 0)]) # (S, 0) 튜플을 포함하는 deque를 생성