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

실버 1 - https://www.acmicpc.net/problem/5014

Code

from collections import deque

F, S, G, U, D = map(int, input().split())

""""
G에 가야함
총 F층으로 이루어져있음
현재 나는 S층

엘베 버튼 U : U층 위로 이동
엘베 버튼 D : D층 아래로 이동
"""

visited = [0 for _ in range(F+1)]

q = deque()
q.append([S, 0])
visited[S] = 1

flag = False

while(q):
    curr = q.popleft()
  
    curr_floor = curr[0]
    curr_cnt = curr[1]

    if(curr_floor == G):
        flag = True
        print(curr_cnt)
        break

    next_floor1 = curr_floor + U
    next_floor2 = curr_floor - D
    if(0 < next_floor1 <= F):
        if(visited[next_floor1] == 0):
            q.append([next_floor1, curr_cnt + 1])
            visited[next_floor1] = 1
    if(0 < next_floor2 <= F):
        if(visited[next_floor2] == 0):
            q.append([next_floor2, curr_cnt + 1])
            visited[next_floor2] = 1

if(flag == False):
    print("use the stairs")

풀이 및 해설

• 전체 순서
  • S에서부터 시작해서 → 이동 가능한 층을 계속 큐에 넣어주며 탐색 → G층에 도착하는 층이 나오면 해당 cnt 출력 → 종료
  • 다 돌아봐도 G층에 못 도착한다면 → 계단 이용 문구 출력
• 적용된 BFS 개념
  • U층 위로 이동 가능 → U층 위로 이동한 층을 q에 추가, 해당 층 방문 처리
  • D층 아래로 이동 가능 → D층 아래로 이동한 층을 q에 추가, 해당 층 방문 처리
• 시간 초과 해결 → 방문 처리를 q에 넣을 때 해줘야 중복 방문 하지 않는다 !