2학년 동계 모각코 5회차

목표 : 이것이 코딩 테스트다 with 파이썬 에 실려있는 알고리즘 문제를 풀어보자.

union, find 연산을 요구하므로 서로소 집합 알고리즘을 구현하여 문제를 해결하도록 한다.

Code

# 팀 결성 문제
# 팀 합치기, 같은 팀 여부 확인하는 연산이므로 서로소 집합 알고리즘을 사용한다.

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

n, m = map(int, input().split())
parent = [0] * (n + 1)

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

for i in range(m):
    oper, a, b = map(int, input().split())
    if oper == 0:
        union_parent(parent, a, b)
    elif oper == 1:
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

문제를 정리해보면 하나의 그래프에서 두 개의 최소신장트리를 만들어내면 된다. 그러므로 하나의 최소신장트리를 구한 뒤 가장 비용이 높은 간선 한 개를 삭제하면 된다.

Code

# 도시 분할 계획 문제

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
v, e = map(int, input().split())
parent = [0] * ( v + 1)

edges = []
result = 0

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

for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

edges.sort()	# 내림차순 정렬
last = 0    # 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선

for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        last = cost

print(result - last)

각 강의에 대해서 선수 과목을 확인 할 때 더 오랜 시간이 걸리는 경우 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구하였다.

Code

# 커리큘럼 문제

from collections import deque
import copy

v = int(input())

indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]
time = [0] * (v + 1)    # 모든 노드의 진입차수를 0으로 초기화

for i in range(1, v + 1):   # 방향 그래프의 모든 간선 정보 입력받음
    data = list(map(int, input().split()))
    time[i] = data[0]
    for x in data[1: -1]:
        indegree[i] += 1
        graph[x].append(i)

# 위상 정렬 함수
def topology_sort():
    result = copy.deepcopy(time)
    q = deque()

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

    while q:
        now = q.popleft()
        for i in graph[now]:
            result[i] = max(result[i], result[now] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in range(1, v + 1):
        print(result[i])

topology_sort()