[이것이 취업을 위한 코딩테스트이다 with 파이썬] Ch.10 그래프 이론

1. 다양한 그래프 알고리즘

이미 배운 내용을 훑어보자

 

- 그래프 알고리즘 유형

• DFS/BFS
• 최단경로
• 크루스칼 알고리즘(그리디)
• 위상 정렬 알고리즘(큐, 스택 자료구조)

 

- 그래프 알고리즘 문제 & 구현 방법

• '서로 다른 개체(혹은 객체)가 연결되어 있다'
• '여러 개의 도시가 연결되어 있다'
• 구현 방법 : 인접 행렬(2차원 배열 사용), 인접 리스트(리스트 사용)     * V : 노드의 개수, E : 선의 개수
  • 인접행렬(플로이드 워셜) - 메모리 정보 O(V**2) (간선 정보 저장하기 위함) / 간선 비용 O(1) (A →B 이동)
  • 인접 리스트(다익스트라) - 메모리 정보 O(E) (간선의 개수만큼)  / 간선 비용 O(V) (A →B 이동)

⭐ 어떤 문제를 만나든 메모리, 시간을 염두해두고 알고리즘 선택하여 구현하기⭐

   ex) 최단 경로 - (노드 개수가 작은 경우) 플로이드 워셜 / (노드와 간선 개수 많은 경우) 다익스트라 알고리즘 

 

- 트리 자료구조

• 우선순위 큐 - 최소 힙(항상 '부모 노드 < 자식 노드' 형태)

 

- 그래프와 트리 비교

---

서로소 집합

 

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

 

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

•  union, find 연산으로 조작할 수 있음
• union(합집합) : 2개의 원소가 포함된 집합 → 하나의 집합으로 합치는 연산
• find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 

 

서로소 집합 자료구조 

- 서로소 집합 자료구조 구현 : 트리 자료구조 이용 

• A'와 B' 중에서 번호 작은 원소가 부모 노드가 되도록 구현 

 

- 예시

• Union 연산들은 그래프 형태 '시각화하여' 표현
  (각 원소의 집합 정보 표현은 트리 자료구조 이용)

{1,2,3,4} {5,6} 두 집합으로 구분

 

- 알고리즘 동작 과정 예시

• union 연산 1개씩 확인 (서로 다른 두 원소에 대해 합집합 수행할 경우) 
  →  각각의 루트 노드 찾기, 큰 루트 노드가 작은 루트 노드 가리키기 
• union 연산을 효과적으로 수행하기 위해, '부모 테이블'을 항상 가지고 있어야 함
• 루트 노드를 찾기 위해, 재귀적으로 부모를 거슬러 올라가야 함(부모 테이블을 확인하며 거슬러 올라가야 함)

노드 3의 루트노드는 1(3&rarr;2&rarr;1)

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 함수가 비효율적으로 동작
예) {1,2,3,4,5}가 연결될 때, 5의 루트노드 1까지 가는데 O(V) 시간이 걸림 

 

 

- 효율적인 알고리즘 코드

• find의 '경로압축' 기법을 적용하여 시간 복잡도 개선
  • 경로압축 : find함수 재귀적 호출 → 부모 테이블값 갱신 

# find_parent 함수 수정
# 재귀함수를 사용하여 최종 리턴함수를 parent[x]에 담음
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

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

 

서로소 집합 알고리즘의 시간 복잡도

- 경로 압축 방법만을 이용할 경우

• 노드의 개수 V, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때 시간복잡도

  예) 노드의 개수 1000, union 및 find 연산이 총 100만 번 수행 → 1000만 번 가량의 연산이 필요

 

 

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

- 사이클 판별 : (union 연산은 그래프에서의 간선으로 표현) 간선을 하나씩 확인, 두 노드가 포함되어 있는 집합을 합치는 과정

• 알고리즘 작동 방식 : (간선의 개수 E개) 모든 간선을 하나씩 확인, 간선에 대해 union 및 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

# 노드의 개수와 간선의 개수 입력받기
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('사이클이 발생하지 않았습니다.')

---

신장 트리

 

- 신장 트리(Spanning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

  (트리의 성립 조건 : 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다) 

• 하나의 그래프에서 여러 개의 신장 트리가 있을 수 있음

 

 

크루스칼 알고리즘

 

- 신장 트리 예시

• N개의 도시가 존재하는 상황 → 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있도록 도로 설치
  (2개의 도시 A,B를 선택했을 때, 도시A에서 도시B로 이동하는 경로가 반드시 존재하도록 도로 설치)
  모든 도시를 '연결'할 때, 최소한의 비용으로 연결하려면?
• 최소 신장 크리 알고리즘 : 신장 트리 중, 최소 비용으로 만들 수 있는 신장 트리 찾는 알고리즘 → 크루스칼 알고리즘

 

- 크루스칼 알고리즘 (그리디)

• 가장 적은 비용으로 모든 노드 연결 가능
• 모든 간선에 대해서 정렬 수행 → 가장 거리가 짧은 간선부터 집합에 포함시킴
  (단, 사이클을 발생시킬 수 있는 간선인 경우는 포함시키지 않는다)
• 신장 트리에 포함되는 간선의 개수 : '노드개수 - 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

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

• 간선을 정렬하는 작업이 가장 오래걸림 → 정렬했을 때, 시간복잡도 O(ElogE)

---

위상정렬

 

- 위상정렬(Topology Sort) : 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘 
• 예시) 선수과목을 고려한 학습 순서 설정 (선후관계가 있다면, 선후관계를 지키는 전체 순서 계산 가능)
• 진입차수(Indegree) : 특정한 노드로 '들어오는' 간선의 개수 의미
• 위상정렬의 답 : 알고리즘 수행 시, 큐에서 빠져나간 노드 순서대로 출력(답안은 여러가지가 될 수 있음)

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개의 팀이 존재한다. 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.

  1) '팀 합치기' 연산은 두 팀을 합치는 연산이다.

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

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

 

✔️ 입력 조건

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

 

✔️ 출력 조건

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

 

✔️ 입출력 예시

✔️ 나의 문제풀이

- 같은 팀 여부 확인은 리스트를 확인하는 것이 아닌, find() 함수 이용하여 확인하기

• 루트 노드 연결되어 있기 때문 

n,m = map(int,input().split())

teams = [i for i in range(n+1)]     # 상위 팀

def find(teams,a):
    if teams[a] != a:
        teams[a] = union(teams,teams[a])
    return teams[a]

def union_answer(teams, a, b):
    a = find(teams, a)
    b = find(teams, b)

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

for _ in range(m):
    idx, a, b = map(int,input().split())
    if idx == 1:
        if teams[b] == teams[a]:
            print('YES')
        else:
            print('NO')
    else:
        union_answer(teams, a, b)

 

✔️ 책의 문제풀이

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

 

✔️ 리뷰

- find값으로 '같은 팀 여부 확인'해야한다! 단순히 리스트 값만 확인하면, 실제로는 같은 루트인데 다른 값이라고 인식할 수 있음

---

📌3. 도시 분할 계획

 

✔️ 문제

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

 

마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. (각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 하고, 마을에는 집이 하나 이상 있어야 한다.)

 

분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오. 

 

✔️ 입력 조건

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

 

✔️ 출력 조건

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

 

✔️ 입출력 예시

 

✔️ 나의 문제풀이

- 해결 못함

- 최소신장트리 이용, 사이클을 만든 것 중 최소...?

n,m = map(int, input().split())

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

edges = []
ans = 0

def find_parent(home,a):
    if home[a] != a:
        home[a] = find_parent(home, home[a])
    return home[a]

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

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


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

edges.sort()

print(edges)

 

✔️ 책의 문제풀이

- 아이디어 : 전체 그래프에서 2개의 최소 신장 트리 만들기 → 크루스칼 알고리즘 (최소 신장 트리 찾은 후, 최소 신장 트리 간선 중 가장 비용이 큰 간선 제거) → 최적의 해 만족 

def find_parent(home,a):
    if home[a] != a:
        home[a] = find_parent(home, home[a])
    return home[a]

def union_parent(home, a, b):
    a = find_parent(home, a)
    b = find_parent(home, b)
    if a < b:
        home[b] = a
    else:
        home[a] = b

n,m = map(int, input().split())
home = [i for i in range(n+1)]
edges = []
ans = 0

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

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

for edge in edges:
    c, a, b = edge
    if find_parent(home,a) != find_parent(home, b):
        union_parent(home,a,b)
        ans += c
        last = c

print(ans - last)

 

✔️ 리뷰

- 최소 신장 트리 코드 익히기

---

📌4. 커리큘럼

 

✔️ 문제

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

 

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

 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.

 

✔️ 입력 조건

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

 

✔️ 출력 조건

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

 

✔️ 입출력 예시

 

✔️ 나의 문제풀이

from collections import deque

n = int(input())
visited = [False] * (n+1)
hour = [0] * (n+1)

q = deque()
for i in range(1,n+1):
    if i == 1:
        a,b = map(int,input().split()) 
        hour[i] = a
        visited[i] = True
    else:
        list_ = list(map(int,input().split()))
        for j in range(1, len(list_)-1):
            q.append((list_[0], list_[j], i))

while q:
    cost, a, b = q.popleft()
    if visited[b]:
        visited[b] = max(visited[b], cost + hour[a])
        continue

    visited[b] = True
    hour[b] = hour[a] + cost

for i in range(1,len(hour)):
    print(hour[i])

 

✔️ 책의 문제풀이

- 아이디어 : 위상 정렬 알고리즘 응용.
각 강의에 대하여 인접한 노드 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우가 있다면 → 더 오랜 시간이 걸리는 경우 시간 값을 저장하여 테이블 갱신

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()

 

✔️ 리뷰

- 진입차수 적용해서 코드 작성하기