상세 컨텐츠

본문 제목

[Baekjoon Online Judge] 백준 11657번 타임머신(Python)

Problem Solving/Baekjoon Online Judge

by HelloMinchan 2020. 6. 12. 20:11

본문

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11657번 타임머신

(Python)

(글쓴날 : 2020.06.12)

 


* Baekjoon Online Judge, 백준 11657번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 11657번 타임머신


1) 문제

문제 링크 : https://www.acmicpc.net/problem/11657

 

11657번: 타임머신

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

www.acmicpc.net


2) 풀이 과정

* 시간 복잡도 : O(EV)

 

N개의 도시와 도시 구간 별 M개의 버스 시간이 주어질 때, 1번 도시에서 나머지 도시로 가는 최소 시간을 구하는 문제입니다.

단, 갈 수가 없는 도시는 -1로 표시하며, 시간에 음수도 포함되어 있으므로 만약 시간이 음의 무한대로 줄어드는 구간이 존재할 경우 -1을 출력 후 종료합니다.

 

저의 경우, 벨만 포드 알고리즘을 적용하였고, Python을 사용했습니다.

우선, 주어지는 정보들을 인접 리스트로 구현한 뒤, 벨만 포드 알고리즘을 적용하여 음의 사이클이 존재하는지 판단하였고, 음의 사이클이 없을 시 최소 시간을 출력하여 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
input = sys.stdin.readline
 
def bellmanFord():
    global isPossible
 
    for repeat in range(N):
        for i in range(1, N+1):
            for wei, vec in adjList[i]:
                if dist[i] != INF and dist[vec] > dist[i] + wei:
                    dist[vec] = dist[i] + wei
                    if repeat == N-1:
                        isPossible = False
 
N, M = map(int,input().split())
adjList = [[] for _ in range(N+1)]
INF = 2147483647
dist = [INF] * (N+1)
dist[1= 0
isPossible = True
 
for _ in range(M):
    a,b,c = map(int,input().split())
 
    adjList[a].append((c,b))
 
bellmanFord()
 
if not isPossible:
    print(-1)
else:
    for d in dist[2:]:
        print(d if d !=INF else -1)

 

관련글 더보기

댓글 영역