참고 교재

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)

실전 문제 1 - 미래 도시

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
n, m = map(int, input().split())
D = [[int(1e9)] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            D[i][j] = 0

for i in range(0, m):
    a, b = map(int, input().split())
    D[a][b] = 1
    D[b][a] = 1

x, k = map(int, input().split())

for a in range(1, n + 1):
    for b in range(1, n + 1):
        for c in range(1, n + 1):
            if a != b and a != c:
                D[a][b] = min(D[a][b], D[a][c] + D[c][b])

distance = D[1][k] + D[k][x]

if distance < int(1e9):
    print(distance)
else:
    print(-1)

일반적으로 파이썬에서의 무한 표현 = int(1e9)
알고리즘 = 플로이드 와셜 알고리즘
점화식 (a에서 b로 가는 최단 경로, k는 경유지)
$D_{ab}=min(D_{ab}, D_{ak}+D_{kb})$
시간 복잡도 = $O(n^3)$

실전 문제 2 - 전보

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def get_smallest_index(D, V):
    min = INF
    idx = 0

    for i in range(1, len(D)):
        if not V[i] and D[i] < min:
            min = D[i]
            idx = i

    return idx

def dijkstra(A, n):
    V = [False] * (n + 1)
    D = [INF] * (n + 1)

    for i in range(1, n + 1):
        D[i] = A[c][i]

    V[c] = True

    for _ in range(n - 1):
        current = get_smallest_index(D, V)
        V[current] = True

        for j in range(1, n + 1):
            if not V[j] and D[current] + A[current][j] < D[j]:
                D[j] = D[current] + A[current][j]

    return D

n, m, c = map(int, input().split())
INF = 1e9
A = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(m):
    x, y, z = map(int, input().split())
    A[x][y] = z

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            A[i][j] = 0

D = dijkstra(A, n)
cnt = 0
time = 0

for x in D[1:]:
    if x != 0 and x < INF:
        cnt += 1
        time = max(time, x)

print(cnt, time)

다익스트라 알고리즘으로 해결 가능
이중 반복문을 사용하면 시간 복잡도 $O(n^2)$
→ 힙으로 개선하면 $O(nlogn)$으로 낮출 수 있음.