[Baekjoon/Python] 5014. 스타트링크 (BFS)
문제
건물에 F층이 있고, 현재 S층에서 G층으로 이동하려고 한다.
엘리베이터 버튼은 두 가지:
- 위로
U층 이동 - 아래로
D층 이동
목표는 최소 버튼 횟수로 G층에 도달하는 것이다.
도달할 수 없다면 "use the stairs"를 출력한다.
풀이 과정
1. BFS로 접근해야 하는 이유
이 문제는 버튼을 한 번 누를 때마다 이동 횟수가 항상 1이다.
즉, 모든 이동 비용이 동일하므로 BFS로 최단 횟수를 구할 수 있다.
2. BFS 핵심 개념
BFS는 이동 횟수 기준으로 다음과 같이 탐색한다.
- 1번 이동
- 2번 이동
- 3번 이동
이 순서로 탐색하기 때문에
처음 방문한 순간이 곧 최소 이동 횟수가 된다.
나의 시행착오
1. 이미 방문한 층도 다시 갱신하려고 했던 접근
처음에는 아래처럼 생각했다.
“이미 방문한 층이라도, 더 적은 횟수로 도달할 수 있지 않을까? 더 짧으면 갱신해야지”
그래서 다음과 같이 코드를 작성했다.
if apt[moved] == 0:
apt[moved] = apt[current] + 1
else:
apt[moved] = min(apt[current] + 1, apt[moved])즉, 더 작은 값이 나오면 갱신하려는 방식이었다.
하지만 이 접근은 BFS에서는 필요 없는 로직이었다.
이 문제는 버튼 한 번 누를 때마다 비용이 전부 같다. 위로 가기 1번, 아래로 가기 1번.
즉 모든 간선의 가중치가 1인 그래프이다.
- BFS는 애초에 최소 횟수부터 탐색 -> 따라서 나중에 더 작은 값이 나올 일이 없음
- BFS: 간선 가중치가 모두 같을 때 최단거리 보장
그래서 처음 방문 = 최소 횟수
이미 방문한 곳을 다시 더 짧게 갱신할 일은 없음
반대로 이런 경우는 다르다.만약 가중치가 다른 상황이면(예를들어 엘리베이터 위로 가면 10초, 아래로 가면 1초)
BFS 안됨. 나중에 더 빠른 경로가 생길 수 있다. (이게 다익스트라)
- 이동 1번, 점프 1번, 버튼 1번처럼 모든 행동 비용이 동일하다 → BFS로 최단거리
- 이동마다 비용이 다르다 → 다익스트라 같은 다른 최단경로 알고리즘 고려
2. 방문 체크 없이 큐에 계속 추가한 문제
또 하나의 문제는 다음 코드였다.
queue.append(moved)방문 여부를 확인하지 않고 무조건 큐에 넣었기 때문에:
- 같은 층이 계속 반복해서 큐에 들어감
- A → B → A → B 무한 반복 구조 발생
- 결국 SIGTERM (강제 종료) 발생
3. dist 배열 초기값 문제
처음에는 0으로 초기화했는데:
- 시작점도
0 - 방문 안 한 곳도
0
이 둘이 구분되지 않아 로직이 꼬였다.
그래서 -1로 초기화하여 명확히 구분하도록 수정했다.
최종 알고리즘
1. dist 배열을 -1로 초기화 (미방문 표시)
2. 시작점 S를 큐에 넣고 dist[S] = 0
3. BFS 수행
-
현재 층에서
- 위로 이동
- 아래로 이동
-
범위 안이고 아직 방문하지 않은 경우만 큐에 추가
4. 목표 G에 도달하면 종료
5. dist[G]가 -1이면 도달 불가
최종 코드
from collections import deque
F, S, G, U, D = map(int, input().split())
dist = [-1] * (F + 1)
dist[S] = 0
queue = deque([S])
while queue:
current = queue.popleft()
if current == G:
break
for moved in (current + U, current - D):
if 1 <= moved <= F and dist[moved] == -1:
dist[moved] = dist[current] + 1
queue.append(moved)
if dist[G] == -1:
print("use the stairs")
else:
print(dist[G])배운 점 및 코테 팁
1. BFS에서는 재방문 갱신이 필요 없다
- 처음 방문이 최단 거리
min()갱신 로직 불필요
2. 방문 체크는 큐에 넣기 전에 한다
- 안 하면 무한 반복
- 시간 초과 / SIGTERM 발생
3. 거리 배열은 -1로 초기화하는 것이 안전하다
- 0 초기화는 시작점과 구분이 안 됨
4. 판단 기준 정리
- 최소 횟수 → BFS
- 이동 비용 동일 → BFS
- 상태 전이 명확 → BFS
