그래프 이론 (Graph)

 

다양한 그래프 알고리즘

- 그래프: 노드 + 간선

    ㄴ '서로 다른 개체(혹은 객체)가 연결되어 있다'

    ㄴ 인접행렬(2차원 배열) - 메모리↑, 시간↓ / 인접리스트(리스트) - 메모리↓, 시간↑

- 그래프 vs 트리

	그래프	트리
방향성	방향 그래프 / 무방향 그래프	방향 그래프
순환성	순환 / 비순환	비순환
루트 노드 존재 여부	X	O
노드간 관계성	X	부모-자식 관계
모델의 종류	네트워크 모델	계층 모델

 

서로소 집합

- 서로소 집합: 공통 원소가 없는 두 집합

- 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

    ㄴ union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

    ㄴ find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

# 그래프 이론
# 기본적인 서로소 집합 알고리즘

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

- 루트 노드가 같은 원소끼리는 동일한 집합을 이룬다. -> {1, 2, 3, 4} / {5, 6}

- 시간복잡도 O(VM)

   ㄴ 노드의 개수 V, find 혹은 union 연산의 개수 M

   ㄴ 루트를 찾기 위해 순서대로 부모 노드를 거슬러 올라가야 함 

- 경로 압축 기법을 통해 시간복잡도 개선 -> find 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신

# 그래프 이론 
# 개선된 서로소 집합 알고리즘 (경로 압축 기법 이용)

# 경로 압축 기법을 이용한 특정 원소가 속한 집합을 찾기
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

# 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=' ')

- 시간복잡도 O(V + M(1 + log(2-M/V)(V))

 

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

- 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.

   (방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별)

# 그래프 이론
# 서로소 집합을 활용한 사이클 판별 소스코드

# 특정 원소가 속한 집합을 찾기
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("사이클이 발생하지 않았습니다.")

 

신장 트리

- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

크루스칼 알고리즘

# 그래프 이론
# 크루스칼 알고리즘

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

- 시간 복잡도 O(ElogE)

   ㄴ 간선을 정렬했을 때의 시간 복잡도

 

위상 정렬

- 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘

- 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

- 그래프상에서 선후관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.

# 그래프 이론
# 위상 정렬

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)

   ㄴ 노드와 간선을 모두 확인

 

실전 문제1. 팀 결성

# 그래프 이론
# 실전 문제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

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

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

for _ in range(m):
    k, a, b = map(int, input().split())

    if k == 0:
        union_parent(parent, a, b)
    else:
        if find_parent(parent, a) == find_parent(parent, b):
            print("YES")
        else:
            print("NO")

 

실전 문제2. 도시 분할 계획

 

# 그래프 이론
# 실전 문제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

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):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

edges.sort()
biggest = 0 # 최소 신장 트리에 포함되는 간선 중 가장 비용이 큰 간선

for edge in edges:
    c, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += c # 최종 결과에 비용 더하기
        biggest = c # 비용 순으로 정렬했기 때문에 현재의 비용이 가장 큰 비용

print(result - biggest) # 최종 결과에서 가장 큰 비용 뺴기

 

실전 문제3. 커리큘럼

# 그래프 이론
# 실전 문제2. 커리큘럼

from collections import deque
import copy

n = int(input())

indegree = [0] * (n+1) # 모든 노드에 대한 진입차수
graph = [[] for i in range(n+1)] # 모든 간선에 대한 정보를 담은 리스트
time = [0] * (n+1) # 강의 시간

for i in range(1, n+1):
    data = list(map(int, input().split()))
    time[i] = data[0] # 강의 시간
    for j in data[1:-1]: # 선수 강의
        indegree[i] += 1
        graph[j].append(i)

def topology_sort():
    # 알고리즘 수행 결과를 담을 리스트
    # 리스트의 경우, 단순히 대입 연산을 하면 값이 변경될 때 문제가 발생할 수 있기 때문에 리스트의 값을 복제해서 사용 -> deepcopy
    res = copy.deepcopy(time)
    # 큐 -> deque
    q = deque()

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

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

    for i in range(1, n+1):
        print(res[i])

topology_sort()