참고 교재

이것이 코딩테스트다 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
28
29
30
n, m = map(int, input().split())
team = []

for i in range(n + 1):
    team.append(i)

def find(team, a):
    if team[a] != a:
        team[a] = find(team, team[a])

    return team[a]

def union(team, a, b):
    a = find(team, a)
    b = find(team, b)

    if a < b:
        team[b] = a
    else:
        team[a] = b

for i in range(m):
    c, a, b = map(int, input().split())
    if c == 0:
        union(team, a, b)
    else:
        if find(team, a) == find(team, b):
            print('YES')
        else:
            print('NO')

전형적인 유니온 파인드 문제

실전 문제 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
n, m = map(int, input().split())

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])

    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

costs = []
parent = [0] * (n + 1)
result = 0
last = 0

for i in range(n + 1):
    parent[i] = i

for i in range(m):
    a, b, c = map(int, input().split())
    costs.append((c, a, b))

costs.sort()

for (c, a, b) in costs:
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += c
        last = c

print(result - last)

최소 신장 트리(MST)를 구한 다음,

그 중에서 가장 작은 간선을 삭제

실전 문제 3 - 커리 큘럼

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
from collections import deque

n = int(input())
edges = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
costs = [0] * (n + 1)

for i in range(1, n + 1):
    t = list(map(int, input().split()))
    costs[i] = t[0]

    if t[1] == -1:
        continue

    for x in t[1:]:
        if x != -1:
            edges[x].append(i)
            indegree[i] += 1

q = deque()

for i in range(1, n + 1):
    if indegree[i] == 0:
        q.append(i)

while q:
    now = q.popleft()

    for x in edges[now]:
        indegree[x] -= 1
        if indegree[x] == 0:
            q.append(x)
            costs[x] += costs[now]

for x in costs[1:]:
    print(x)

전형적인 위상 정렬 문제