[BOJ] 백준 5014 스타트링크 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

강호가 엘리베이터를 타고 S층에서 G층으로 가기 위한 최소 이동 횟수를 구하는 문제이다.

이 문제의 특징은 한 번에 하나의 버튼만 눌러 Up 또는 Down 크기만큼만 이동할 수 있다.

 

너비 우선 탐색을 수행하여 문제를 풀면 목적지까지 최소 횟수로 이동하게 할 수 있다.

 

visited 배열을 대신하여 cnt 배열을 사용했다.

cnt 배열은 기본값이 -1로 초기화되어있고, 출발선은 0으로 설정을 한다.

Up 또는 Down 선택을 큐에 넣을 때마다 cnt 배열에 그 위치값을 이전 위치 값 +1로 설정한다.

 

최종 목적지인 g까지 도착하는 최소 이동 횟수가 cnt[g]에 구해지게 된다.

 

 

 

구현 언어: Python

 

from collections import deque


def solve():
    global total, kangho, up, down, cnt
    queue = deque()
    queue.append(kangho)
    cnt[kangho] = 0
    
    while queue:
        now = queue.popleft()
        for next in (now + up, now - down):
            if 1 <= next <= total:
                # 아직 방문하지 않은 층
                if cnt[next] == -1:
                    cnt[next] = cnt[now] + 1
                    queue.append(next)


total, kangho, dest, up, down = map(int, input().split())
cnt = [-1] * (total+1)
solve()

# 여전히 -1이라면 그 층에 갈 수 없다는 뜻
if cnt[dest] == -1:
    print("use the stairs")
else:
    print(cnt[dest])