SW사관학교 정글

[SW 정글] WEEK03 개발일지(그래프 이론, BFS, DFS, 위상 정렬)

SalmonSushi 2022. 4. 22. 14:18

* 앞으로 한 주의 공부가 마무리되는 목요일에 개발일지를 쓰기 위해 노력해보려 합니다..

 

 오늘(쓰는 시점 목요일) week03 그래프 이론에 대한 주차가 끝났다. 끝난 기념으로 역시 시험을 보았고, 이번에는 다행히 모든 문제를 풀 수 있었다. 특히 마지막 문제였던 '백준 1939 중량제한' 문제는 시험 중에 크루스칼 알고리즘을 변형한 기가막힌 풀이가 떠올라 잘 풀어서 뿌듯했다. 시간도 잘 나와서 파이썬 중에 3등으로 올려놓았다. 이와 별개로 다른 분들의 '중량제한' 풀이 또한 기가막혀서 이에 대해서는 아래 글에서 좀 다루어보려고 한다. 그럼 이제 이번주차 그래프 이론 공부 내용 중 인상깊었던 내용을 좀 정리해보겠다.

Week03 알고리즘 주제 : 그래프(vertex, edge node, arc), BFS, DFS, 위상 정렬

 이번주 공부 주제들 중 기초 그래프 이론과 BFS, DFS는 이미 공부했던 내용이지만 위상 정렬(Topology Sort)은 이번에 처음 공부했고, 상당히 재미있게 공부했다. 이번에 풀었던 문제들 중 재밌게 풀었던 '1197 최소 스패닝 트리', '21606 아침 산책', '1948 임계경로' 문제들 중 이미 블로그에 정리한 '아침 산책' 문제를 제외한 두 문제와 시험에 나왔던 '1939 중량제한' 문제를 정리해보도록 하겠다.

 

[백준] 1197 최소 스패닝 트리 - Kruskal 알고리즘

 MST(Minimum Spanning Tree). 다른 말로는 최소 신장 트리, 최소 스패닝 트리라고도 부른다. 여기서 스패닝 트리란 그래프 내의 모든 정점(노드, vertex)을 최소한의 간선으로(V-1개)로 포함하는 트리를 말하며, 그 중 MST는 간선 전체의 비용(cost, 가중치) 합이 최소인 스패닝 트리를 말한다. 문제에서 모든 노드를 최소 비용으로 연결하고자 하는 경우 MST 문제라 생각할 수 있을 것이다.

 그래프에서 MST를 구하는 방법으로 Prim 알고리즘과 Kruskal 알고리즘이 있으며, 이 문제에서는 Kruskal 알고리즘을 사용했다.

Kruskal 알고리즘

 Greedy한 알고리즘이다. 그래프의 모든 엣지를 리스트에 담아 가중치에 대해 오름차순으로 정렬한 뒤, 스패닝 트리 조건을 유지하기 위해 고른 엣지가 사이클을 만들지 않도록 신경쓰며(Union-Find 활용) 가중치가 작은 엣지부터 차례대로 V-1개 고른다. 시간복잡도는 edge들을 정렬하는 데 걸리는 시간인 O(ElgE)이다.

 

* Kruskal 알고리즘에 대한 자세한 내용은 해당 블로그를 참고했다.

 

 구현 코드는 아래와 같다.

# 1197 최소 스패닝 트리
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
edge_list = [tuple(map(int, input().split())) for _ in range(E)]
edge_list.sort(key=lambda x:x[2]) # 가중치에 대해 오름차순 정렬

# Union-Find
group_info = list(range(V+1))
def find_group(node):
    """node가 속한 그룹을 리턴하고 그룹 관계를 최적화해줌(노드의 그룹명을 대빵에 맞게 바꿔줌)"""
    if group_info[node] == node: # 그룹의 대표 노드이면
        return node
    group_info[node] = find_group(group_info[node])
    return group_info[node]

def union(node_1, node_2):
    """node_1과 node_2의 그룹을 합쳐줌"""
    group_1 = find_group(node_1)
    group_2 = find_group(node_2)
    if group_1 > group_2: # 더 작은 그룹명을 따라주기 위해
        group_1, group_2 = group_2, group_1
    group_info[group_2] = group_1 # 그룹의 대빵을 갈아끼워줌

# Kruscal
total_cost, edge_cnt = 0, 0
for a, b, cost in edge_list:
    if find_group(a) != find_group(b): # 그룹이 다르면(같으면 사이클)
        union(a, b)
        total_cost += cost
        edge_cnt += 1
        if edge_cnt == V-1: # 엣지를 전부 찾았으면
            break

print(total_cost)

 

[백준] 1948 임계경로 - 위상 정렬

 위상정렬(Topology Sort)은 DAG(Directed Acyclic Graph)의 정점을 선형으로 정렬한 것이다. 여기서 DAG란 이름 그대로 사이클이 없는 유향 그래프를 말한다. DAG를 만족하는 대표적인 경우는 한 집단 내에서 두 개의 대상을 골라 대소비교를 한 정보가 여러번 주어지는 경우가 있다.

어떤 문제가 위상정렬 문제일까?

 DAG(Directed Acyclic Graph)인 문제면 거의 위상 정렬을 활용할 수 있는 문제인 것으로 보인다.

 

그럼 어떤 그래프가 DAG일까?(예시)

   - 여러 대상이 있는 그룹에서 두 개를 골라 대소비교를 여러번 해 정렬하고자 하는 경우

   - 특정 부품들이 조립 관계에 있는 경우

     => 특정 방향으로 선후 관계에 있는 경우 DAG

위상정렬(Topology Sort) 알고리즘 절차

 위상정렬 알고리즘은 해당 블로그 글을 참고하였다.

  1. 그래프의 인접 리스트를 만들고, 만드는 과정에서 자기자신을 가리키는 노드가 몇 개인지 카운트해 in_degree에 저장해준다.
  2. in_degree의 값이 0인 노드는 자신에게 들어오는 노드가 없다는 뜻이므로 가장 앞에 있는 노드이다. 해당 노드를 res와 queue에 넣어준다.
  3. queue에 대해 반복문을 돌아주는데, queue에서 꺼낸 노드의 인접 노드들의 in_degree값을 1씩 낮춰준다. 그리고 해당 인접노드의 in_degree 값이 0이되면 queue에 넣어준다.

문제 풀이

임계경로 문제를 푸는 데 위의 위상정렬 알고리즘을 활용했다. 푸는 과정에서 시간, 메모리복잡도를 줄이기 위해 굉장히 많은 시행착오가 있었고, 조금씩 시간과 메모리를 줄이고 오류를 잡으며 상당한 성취감을 느꼈다.

 중요한 아이디어 두 가지는 다음과 같다.

  1. 위상정렬을 통해 출발점에서부터 순서대로 순회를 하며 가중치를 더한다. 이 때 각 노드는 자신에게 들어오는 각 노드의 비용 중 최대 비용과 그 최대 비용이 어느 노드로부터 기원했는지 저장한다.(하나의 노드에는 하나의 비용만 저장 / 아래 코드의 path_info 변수)
  2. 위에서 각 노드에 저장했던 최대 비용의 기원 노드 정보를 바탕으로 방문했던 모든 path를 카운트한다.(BFS 활용)

구현 코드

from collections import deque
import sys
input = sys.stdin.readline
n, m = int(input()), int(input())
in_degree = [0]*(n+1)
adj_list = [[] for _ in range(n+1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    adj_list[a].append((b, c))
    in_degree[b] += 1

start, end = map(int, input().split())

queue = deque([start])
path_info = [[0, []] for _ in range(n+1)] # 각 노드를 거치는 path들 중 가장 크거나 같은 애들만 저장(cost, [prev_node_1, prev_node_2...])
path_info[start][1].append(None)
while queue:
    now_node = queue.popleft()
    cost = path_info[now_node][0]
    for adj_node, adj_cost in adj_list[now_node]:
        # 현재 노드(now_node)로 들어온 path들에 대해 인접 노드(adj_node)로 가는 경로 업데이트
        if path_info[adj_node][1]: # path가 들어 있으면
            adj_max_cost = path_info[adj_node][0]
            if cost+adj_cost == adj_max_cost: # 노드 추가
                path_info[adj_node][1].append(now_node)
            elif cost+adj_cost > adj_max_cost:
                path_info[adj_node][0] = cost + adj_cost
                path_info[adj_node][1] = [now_node]
        else: # path가 비어 있는 경우
            path_info[adj_node][0] = cost + adj_cost
            path_info[adj_node][1].append(now_node)
        
        in_degree[adj_node] -= 1    
        if in_degree[adj_node] == 0:
            queue.append(adj_node)

max_cost = path_info[end][0]

path_cnt = 0
visited = [0] * (n+1)
last_queue = deque([end])
while last_queue:
    now_node = last_queue.popleft()
    if now_node == start:
        continue
    for adj_node in path_info[now_node][1]:
        path_cnt += 1
        if adj_node is not None and not visited[adj_node]:
            last_queue.append(adj_node)
            visited[adj_node] = 1

print(max_cost)
print(path_cnt)

[백준] 1939 중량 제한 - Kruskal, 이분 탐색, Dijkstra 알고리즘

 이 문제는 week03 마무리 코딩 테스트에서 나왔던 세 번째 문제(상 난이도)였다. 이 문제를 포스팅하는 이유는 내 풀이가 맘에 드는 것도 있지만, 다른 분들의 풀이를 보며 똑같은 문제를 전혀 다른 방법으로 풀 수도 있다는 것을 느꼈기 때문이었다. 나는 문제를 푸는데 Kruskal 알고리즘에서 아이디어를 얻어서 Union-Find를 사용해 해결했지만, 이분탐색, Dijkstra 알고리즘을 활용해서도 풀 수 있어 놀랐다. 일단 내 풀이 방법을 정리하고, 이분탐색, Dijkstra를 활용한 풀이를 코드 없이 아이디어만 간단히 적어보고자 한다.

Union-Find를 활용한 풀이

방법은 매우 간단하다.

  1. edge 리스트를 다리가 버틸 수 있는 중량에 대해 내림차순으로 정렬한다.
  2. for문을 돌며 높은 중량을 버틸 수 있는 edge부터 뽑아 Union-Find 알고리즘으로 뽑힌 두 노드를 같은 그룹으로 묶어준다.
  3. start 노드와 end 노드가 같은 그룹에 속하게 되면 for문을 종료하고 그 때의 중량을 프린트한다.

 이 풀이는 edge를 내림차순으로 정렬하고 하나씩 뽑는 점과 union-find를 활용한다는 점에서 Kruskal 알고리즘과 유사하다.

 구현한 코드는 아래와 같다.

# 1939 중량제한
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
adj_list = [{} for _ in range(N+1)]
edges_list = [tuple(map(int, input().split())) for _ in range(M)]
edges_list.sort(key=lambda x:x[2], reverse=True)

start, end = map(int, input().split())

group = list(range(N+1))
def find_group(node):
    """node가 속한 그룹 리턴 및 최적화"""
    if group[node] == node:
        return node
    group[node] = find_group(group[node]) 
    return group[node]

def union(node_1, node_2):
    """node_1과 node_2의 그룹을 같은 그룹으로 묶어줌"""
    group_1 = find_group(node_1) 
    group_2 = find_group(node_2)
    if group_1 > group_2: 
        group_1, group_2 = group_2, group_1
    group[group_2] = group_1 

for a, b, weight in edges_list:
    union(a, b)
    if find_group(start) == find_group(end):
        max_weight = weight
        break

print(max_weight)

그 외의 풀이 아이디어

  1. 이분 탐색 활용 풀이 : x라는 중량을 가진 물체가 start에서 end까지 도달할 수 있는지 시도(BFS or DFS 활용)해보고 성공하면 무게를 높이고, 실패하면 무게를 낮춰본다.(이분탐색 / 이 풀이는 '2110 공유기 설치' 문제의 풀이와 매우 유사하다)
  2. Dijkstra 알고리즘 활용 풀이 : 최대힙을 활용해 현재 선택이 가능한 edge(queue에 들어 있는)들 중에 매번 중량이 최대인 edge를 골라 end까지 도달하는 데 사용된 edge 중 가장 중량이 작았던 값을 프린트한다.

이처럼 아예 다른 세 가지 방법으로 문제를 풀 수 있다.

 

Week03를 마치며

 이곳에 오기 전에도 그래프 공부는 좀 했었지만 MST, Kruskal 알고리즘, Union-Find와 같은 몰랐지만 중요한 알고리즘들을 익힐 수 있어서 좋았다. 새로운 주차인 week04의 주제인 그리디와 다이나믹 프로그래밍.. 어려운 파트라 좀 걱정되긴 하지만 다음 주차는 더 열심히 해서 더 많은 것을 얻어갈 수 있도록 하자. 화이팅~~