성능 요약
메모리: 32140 KB, 시간: 440 ms
분류
벨만–포드, 그래프 이론, 최단 경로
문제 설명
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
출력
만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.
00. 발상
- 가장 '전형적인' Bellman-Ford 문제라는 생각이 먼저 들었다.
이와 관련해 이전에 '웜홀' 문제를 풀었던 적이 있는데, 당시에는 음수 사이클이 존재하는지만 체크하는 문제였다.
이번 문제는 음수 사이클 체크에 더해, 만약 음수 사이클이 없다면 시작 노드 1에서부터 다른 노드까지 Bellman-Ford를 통해 구한 최소 거리를 출력해주면 된다.
이전 관련 글
- 99클럽 코테 스터디 4일차 TIL <Baekjoon - [Gold III] 웜홀 - 1865>
https://velog.io/@takealittletime/99클럽-코테-스터디-4일차-TIL-Baekjoon-Gold-III-웜홀-1865- 최단 거리 알고리즘 (Dijkstra, Bellman-Ford, Floyd Warshall)
https://velog.io/@takealittletime/최단-거리-알고리즘-Dijkstra-Bellman-Ford-Floyd-Warshall
01. 코드 작성
# 빠른 입력을 위해 sys.stdin 사용
import sys
input = sys.stdin.readline
# maxsize를 INF로 선언해 사용
INF = sys.maxsize
def bellmanFord(start):
# 시작점->시작점 거리를 0으로 설정 후 Bellman-Ford 이용
distance[start] = 0
# N-1번 반복
for _ in range(N - 1):
for curr, next, cost in bus:
if distance[curr] != INF and distance[next] > distance[curr] + cost:
distance[next] = distance[curr] + cost
# N번째 반복에서 음수 사이클 확인
for curr, next, cost in bus:
if distance[curr] != INF and distance[next] > distance[curr] + cost:
return False # 음수 사이클 존재 시 False 반환
# 음수 사이클이 없으면 True 반환
return True
N,M = map(int,input().split())
bus = list(tuple(map(int,input().split())) for _ in range(M))
distance = [INF] * (N+1)
# 시작점 1로부터 다른 점까지의 거리를 bellmanFord로 계산
# 음수 사이클이 없다면 다른 점까지의 거리 출력
if bellmanFord(1):
for i in range(2,len(distance)):
if distance[i] >= INF:
print(-1)
else:
print(distance[i])
# 음수 사이클이 있으면 -1 출력
else:
print(-1)02. 느낀 점 및 회고
-
99클럽을 시작하고 최단 거리 알고리즘을 다루는 문제들이 여러 번 나왔었다.
해당 유형들을 반복해서 풀고 숙달하다보니, 이제 문제만 읽고도 어떤 알고리즘을 써야 하는지 눈에 보이기 시작했다. -
각 유형에 대해 반복 학습을 통해 유형 별 풀이 방법을 머릿속에 넣어놓는 것이 코딩 테스트를 준비하는데 가장 좋은 방법이 되겠구나, 하는 생각이 들었다.
99클럽 #TIL #개발자취업 #코딩테스트준비 #항해99
