[백준/Python] 스타트링크

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

5014번: 스타트링크

이 문제를 처음 보면 그래프 문제일 것이라고 쉽게 생각나지 않는다. 문제의 예시를 자세히 살펴보면 왜 이 문제가 그래프 문제인지 알 수 있다. 그 이유는 다음 그림을 참고하면 된다.

 

 

from collections import deque

F, S, G, U, D = map(int, input().split())
dist = [0] * (F+1) # 방문 확인 리스트

def bfs(start):
    queue = deque([[start, 0]]) # 시작 위치 큐에 삽입
    dist[start] = 1 # 시작 위치 방문 처리

    while queue:
        x, count = queue.popleft() # 현재 위치, 지금까지 이동한 횟수
        if x == G: # 이동하려는 위치에 도달하면 이동 횟수 리턴
            return count

        if x + U <= F and not dist[x + U]: # 위로 U층 이동
            queue.append([x + U, count + 1])
            dist[x + U] = 1
        if  x - D >= 1 and not dist[x - D]: # 아래로 D층 이동
            queue.append([x - D, count + 1])
            dist[x - D] = 1

    return 'use the stairs' # 이동하려는 위치에 도달하지 못한 경우

answer = bfs(S)
print(answer)

1. 필요한 정보를 입력받고 방문 확인을 위한 변수를 생성한다.

2. BFS를 수행한다.

    2-1. 시작 위치를 큐에 삽입하고 방문처리를 한다.

    2-2. 이동하려는 위치에 도달하면 이동 횟수(count)를 리턴한다.

    2-3. 위로 U층 이동, 아래로 D층 이동한다. 두 위치를 큐에 삽입하고 방문처리를 한다.

    2-4. 이동하려는 위치에 도달하지 못하는 경우 'use the stairs'를 리턴한다.

3. 결과를 출력한다.