참고 교재

이것이 코딩테스트다 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)$으로 낮출 수 있음.