[백준 5014] 스타트링크 (Python)

문제 :

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

5014번: 스타트링크

 

Step 1. 문제 이해하기

• F : 건물 높이, S : 현재 위치, G : 도착 지점, U : 위로 U만큼 이동, D : 아래로 D만큼 이동
• 한 지점에서 갈 수 있는 경우의 수는 2가지(S + U , S - D)
• 버튼을 누르는 최소 횟수 -> 최단 경로

 

Step 2. 문제 풀이 생각하기

1. 'S에서 가장 먼저 G지점에 도착할 때, 최소 횟수를 출력해보자'라고 생각했습니다.
2. 그리고 '어떠한 방식으로도 G에 도달할 수 없는 경우를 대비해서 visited를 생성해야겠다'라고 생각했습니다.
3. 비슷한 문제 : 숨바꼭질

 

Step 3. 차근차근 구현하기

import sys
from collections import deque
input = sys.stdin.readline
f, s, g, u, d = map(int, input().split())
d = [u, -d] # 방향

# 도착지점이 시작지점보다 낮은 곳에 있는 데 d가 0이거나 도착지점이 시작지점보다 높은 곳에 있는데 u이 0일 경우 예외처리
if (s > g and d == 0) or (s < g and u == 0):
    print("use the stairs")
    exit()

def bfs(f, s, g, u, d):
    q = deque()
    q.append([s, 0]) # 데큐에 [현재 지점, 횟수] 저장
    visited = set() # 중복으로 저장하지 않도록 set을 사용
    while q:
        s, cnt = q.pop()
        visited.add(s) # 큐에서 꺼낼 때마다 방문 체크
        # 도착지점에 도달했다면 횟수를 출력하고 프로그램 종료 -> 가장 먼저 도착한 지점이 최소 값이기 때문
        if s == g:
            print(cnt)
            exit()
        # 현재 지점(s)에서 up 또는 down 두가지 경우 실행
        for k in range(2):
            ns = s + d[k] # new start
            if ns > f or ns < 1: # 올라갔는데 총 높이보다 높아지거나 내려갔는데 0층 이하이면 넘어가기
                continue
            # 방문하지 않은 곳일 때만 visited에 층수 저장 및 큐에 [다음 지점, 횟수 + 1]을 저장
            if ns not in visited:
                visited.add(ns)
                q.append([ns, cnt + 1])
    print("use the stairs") # 도달할 수 없다면 해당 문장 출력
bfs(f, s, g, u, d)

 

Step 4. 피드백

처음에는 visited = [0 for _ in range(f + 1)] 로 설정해서 40% 테스트 케이스에서 시간 초과가 발생했는데

모든 지점을 visited로 만들지 않아도 set을 이용해서 방문할 때마다 값이 있는 지 확인하고 값을 넣는 것이 더 빠르다는 것을 배웠습니다.