[이코테] Chap 10. 그래프 이론

Coding Test/이코테

[이코테] Chap 10. 그래프 이론

ʕ민지ʔ 2024. 10. 14. 09:44

이론

그래프 복습

그래프
- 노드(Node)와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조
- '서로 다른 개체(객체)가 연결되어 있다' -> 그래프 알고리즘
- 그래프 중 트리 자료구조는 다양하게 사용됨
  - 부모에서 자식으로 내려오는 계층적인 모델
  - 최소 힙, 최대 힙

그래프 구현 방법
- 2가지의 방식은 메모리와 속도 측면에서 구별됨
- 노드의 개수가 V, 간선의 개수가 E인 그래프

인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식
- 메모리: 간선 정보를 저장하기 위한 O(V^2)
- 시간: 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있음
- 플로이드 워셜 알고리즘
  - 최단 경로를 찾을 때, 노드의 개수가 적은 경우
인접 리스트(Adjacency List): 리스트를 사용하는 방식
- 메모리: 간선의 개수만큼인 O(E)
- 시간: 인접 리스트를 이용할 때는 O(V)만큼의 시간 소요
- 다익스트라 최단 경로 알고리즘 (우선순위 큐)
  - 최단 경로를 찾을 때, 노드와 간선의 개수가 모두 많은 경우

서로소 집합

서로소 집합(Disjoint Sets): 공통 원소가 없는 두 집합
서로소 집합 자료구조
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 연산
  - union(합집합): 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  - find(찾기): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
- union-find(합치기 찾기) 자료구조라고 불리기도 함
서로소 집합 계산 알고리즘
1. union (합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
  1. A와 B의 루트 노드 A', B'를 각각 찾음
  2. A'를 B'의 부모 노드로 설정 (B'가 A'를 가리키도록 함)
2. 모든 union (합집합) 연산을 처리할 때까지 1번 과정을 반복
실제 구현 시, 더 작은 번호를 부모 노드로 설정
각각 루트 노드를 찾아 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 함
예시
- 전체 집합 [1, 2, 3, 4, 5, 6]
- 4개의 union 연산
  - union 1,4
  - union 2,3
  - union 2,4
  - union 5,6
- union 연산의 숫자들은 각각 같은 집합이라는 의미를 가짐
- 그래프로 생각할 수 있음
  - 6개의 노드, 4개의 간선
  - 각 원소의 집합 정보를 표현하기 위해, 트리 자료구조 이용

기본적인 서로소 집합 알고리즘 특징
- 노드 간의 관계 빠르게 확인 가능
- union 연산을 효과적으로 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 함
- 루트 노드를 즉시 계산 할 수 없고, 부모 테이블을 계속해서 확인하며 거슬러 올라가야 함
코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return 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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# Union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

문제점
- find 함수가 비효율적으로 동작함
- 최악의 경우 모든 노드를 확인하여 O(V)의 시간 복잡도
- 예시
  - [1,2,3,4,5]
  - union(4,5) union(3,4) union(2,3) union(1,2)
  - 노드 5의 루트를 찾기 위해 '노드 5 -> 4 -> 3 -> 2 -> 1' 거슬러 올라가야 함

경로 압축 기법 (path compression)
- find 함수 최적화 -> 시간 복잡도 개선
- find 함수를 재귀적으로 호출한 뒤 부모 테이블을 갱신함
- 각 노드에 대하여 find 함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 됨
- 루트 노드에 더욱 빠르게 접근할 수 있으므로 시간 복잡도 개선됨

def find_parent(parent, x):
	# 루트노드가 아니라면, 루트노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
        # 기존 코드는 return find_parent(parent, parent[x])
    return parent[x] # 기존 코드는 return x

서로소 집합을 활용한 사이클 판별

간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것으로 사이클 판별 가능
알고리즘
1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
  1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
  2. 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

cycle = False # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

신장 트리

신장 트리
- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
- 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건 = 트리의 조건

최소 신장 트리 알고리즘
- 최소한의 비용으로 구성되는 신장 트리 찾기
- 예시
  - N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우
  - 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치
크루스칼 알고리즘
- 대표적인 최소 신장 트리 알고리즘
- 그리디 알고리즘으로 분류됨
- 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키되, 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않음
- 알고리즘
  1. 간선 데이터를 비용에 따라 오름차순으로 정렬
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
    1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
    2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
  3. 모든 간선에 대하여 2 번의 과정을 반복

[step 1] 간선 정보만 빼서 정렬 수행 - 간선 9개

[step 2] 가장 짧은 간선인 (3,4) 선택해서 union 함수 수행

[step 3] 사이클이 발생하지 않는 간선에 대해, 짧은 간선 순서대로 union 진행

[step 4] (6,7) 선택해서 확인하는데 이미 동일한 집합이므로 union 하지 않음

[step 5] 마지막까지 반복적으로 진행

최소 신장 트리에 포함되어 있는 간선의 비용을 모두 더하면 최종 비용에 해당함. 위 예시에서는 159.

# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
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()

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)

시간 복잡도
- 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도
- 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업
- 크루스칼 내부에서 사용되는 서로소 집합 알 고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작으므로 무시

위상 정렬

정렬 알고리즘의 일종
방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'
예시
- '선수과목을 고려한 학습 순서 설정'
- 자료구조 -> 알고리즘 / 자료구조 & 알고리즘 -> 고급 알고리즘
- 적절한 순서: 자료구조 -> 알고리즘 -> 고급 알고리즘
진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
- 고급 알고리즘의 진입차수는 2
위상 정렬 알고리즘
1. 진입차수가 0인 노드를 큐에 넣는다
2. 큐가 빌 때까지 다음의 과정을 반복한다.
  1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
  2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
큐가 빌 때까지 큐에서 원소를 계속 꺼내서 처리하는 과정을 반복함
- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단
- 다시 말해 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다.
- 사이클이 존재하는 경우 사이클에 포함되어 있는 원소 중 에서 어떠한 원소도 큐에 들어가지 못하기 때문이다.
기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많음 -> 고려X

[step 1] 진입 차수가 0인 노드를 큐에 넣음 -> 노드 1 삽입

[step 2]

큐에 들어있는 노드 1을 꺼내고, 노드 1과 연결되어 있는 간선들을 제거함.

진입 차수가 0인 노드 2, 노드 5를 큐에 삽입

[step 3]

노드 2 꺼내고 연결된 간선들 제거, 진입차수 0인 노드 3 큐에 삽입

[step 4]

노드 5 꺼내고 연결된 간선 제거, 진입차수 0인 노드 6 큐에 삽입

[step 5]

노드 3 꺼내고 연결된 간선 제거. 진입차수 0인 노드 없으므로 넘어감

[step 6]

노드 6 꺼내고 연결된 간선 제거, 진입차수 0인 노드 5 큐에 삽입

[step 7]

노드 4 꺼내고 연결된 간선 제거, 진입차수 0인 노드 7 큐에 삽입

[step 8]

노드 7 꺼내고 연결된 간선 제거. 진입차수 0인 노드 없으므로 넘어감 -> 끝

위 과정을 수행하는 동안 큐에서 빠져나간 노드를 순서대로 출력한 것이 위상 정렬을 수행한 결과
위상 정렬의 답안은 여러 가지가 될 수 있음
만약에 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면, 여러 가지의 답이 존재하게 됨

from collections import deque

# 노드의 개수와 간선의 개수를 입력 받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v + 1)]

# 방향 그래프의 모든 간선 정보를 입력 받기
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b) # 정점 A에서 B로 이동 가능
    # 진입 차수를 1 증가
    indegree[b] += 1

# 위상 정렬 함수
def topology_sort():
    result = [] # 알고리즘 수행 결과를 담을 리스트
    q = deque() # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    # 위상 정렬을 수행한 결과 출력
    for i in result:
        print(i, end=' ')

topology_sort()

노드와 간선을 모두 확인하므로 O(V+E)의 시간이 소요된다

실전 문제

2. 팀 결성

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산 을 사용할 수 있다.

팀 합치기 연산은 두 팀을 합치는 연산이다.
같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.

선생님이 M개의 연산을 수행할 수 있을 때. '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.

[입력 조건]

첫째 줄에 N. M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 s N.MS 100,000)
다음 M개의 줄에는 각각의 연산이 주어진다.
'팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다 는 의미이다.
'같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는 지를 확인하는 연산이다.
a와 b는 N 이하의 양의 정수이다.

[출력 조건]

'같은 팀 여부 확인' 연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

코드

# 특정 원소가 속한 집합을 찾기
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())
    # 합치합(Union) 연산인 경우
    if oper == 0:
        union_parent(parent, a, b)
    # 찾기(Find) 연산인 경우
    elif oper == 1:
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

3. 도시 분할 계획

동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해 야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을 에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리 된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임 의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만 족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그 램을 작성하시오.

[입력 조건]

첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M은 1 이상 1,000,000 이하인 정수이다.
그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집 과 B번 집을 연결하는 길의 유지비가 C(1 sCS 1.000)라는 뜻이다.

[출력 조건]

첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력한다.

코드

크루스칼 알고리즘으로 최소 신장 트리를 찾은 후, 가장 큰 간선을 제거해 2개로 만든다.

# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(Union 연산)의 개수 입력받기
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)

4. 커리큘럼

동빈이는 온라인으로 컴퓨터공학 강의를 듣고 있다. 이때 각 온라인 강의는 선수 강의가 있을 수 있 는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 예를 들어 '알 고리즘' 강의의 선수 강의로 '자료구조와 '컴퓨터 기초가 존재한다면. 자료구조와 '컴퓨터 기초'를 모 두 들은 이후에 알고리즘' 강의를 들을 수 있다.

동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시 에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N = 3일 때. 3번 강의의 선수 강의로 1번과

2번 강의가 있고, 1번과 2번 강의는 선수 강의가 없다고 가정하자. 그리고 각 강의에 대하여 강의 시 간이 다음과 같다고 가정하자.

1번 강의: 30시간
2번 강의: 20시간
3번 강의: 40시간

이 경우 1번 강의를 수강하기까지의 최소 시 간은 30시간, 2번 강의를 수강하기까지의 최 소 시간은 20시간, 3번 강의를 수강하기까지 의 최소 시간은 70시간이다. 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때. N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.

[입력 조건]

첫째 줄에 동빈이가 듣고자 하는 강의의 수 N(1 s N S 500)이 주어진다.
다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 자 연수로 주어지며, 각 자연수는 공백으로 구분한다. 이때 강의 시간은 100.000 이하의 자연수이다.
각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 1로 끝난다.

[출력 조건]

N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다.

코드

from collections import deque
import copy

# 노드의 개수 입력받기
v = int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v + 1)]
# 각 강의 시간을 0으로 초기화
time = [0] * (v + 1)

# 방향 그래프의 모든 간선 정보를 입력받기
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() # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 원소 꺼내기
        now = q.popleft()
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            result[i] = max(result[i], result[now] + time[i])
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    # 위상 정렬을 수행한 결과 출력
    for i in range(1, v + 1):
        print(result[i])

topology_sort()

Q 43)

import sys
input = sys.stdin.readline

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)


edges = []
result = 0

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

for _ in range(m):
    x, y, z = map(int, input().split())
    edges.append((z, x, y))

edges.sort()
total = 0

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

print(total-result)

현재글[이코테] Chap 10. 그래프 이론

꾸준히

Today :
Yesterday :

일	월	화	수	목	금	토
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

꾸준히