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

18 Aug 2021

[백준] 5014 - 스타트링크

문제 출처: https://www.acmicpc.net/problem/5014
알고리즘:
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색

풀이 - BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
F,S,G,U,D = map(int, input().split())

ud=[U,D*(-1)] # Up, Down
visited=[0]*(F+1)

def bfs(s,g):
    queue=[(s,0)]
    visited[s]=1
    while queue:
        s=queue[0][0]
        cnt=queue[0][1]
        if s==g: #S층 -> G층으로 갈 수 있는 경우
            return cnt
        queue.pop(0)
        for i in range(len(ud)):
            next_s=s+ud[i]
            if 1<=next_s<=F and visited[next_s]==0:
                queue.append((next_s,cnt+1))
                visited[next_s]=1
    return "use the stairs"

print(bfs(S,G))

건물이 1층~F층으로 이루어져 있으므로, 다음 이동하는 층의 범위를 1 ≤ next_s ≤ F로 설정
방문 검사 배열 visited[ ] 을 통해 이전에 이동했던 층으로의 중복 이동을 방지

algorithms