그래프

외판원 순회 문제외판원 순회 문제란 도시들과 도시 간 이동 비용이 주어졌을 때, 외판원이 각 도시를 한 번씩 방문하고 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다. 외판원 순회 문제는 아직 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다.브루트포싱으로는 무려 $O(N!)$의 시간이 걸리며, 오늘 소개할 DP를 이용한 방법으로는 $O(N^22^N)$의 시간이 걸린다. 어떻게 해결할까?1. 완전 탐색 - $O(N!)$외판원이 도시를 방문하는 순서를 모두 구한 후, 최소 비용을 찾는 방법이다.이는 $N$개의 도시를 나열하는 모든 경우를 탐색하는 것으로 $O(N!)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^22^N)$완전 탐색에서는 이미 계산한 경로의 최소 비용을 중복 계산하게..

위상 정렬이란?위상 정렬이란 방향 비순환 그래프의 각 노드를 순서대로 배열하는 것을 의미한다. 가장 대표적인 예시로는 "순서가 정해져 있는 작업들을 정렬하는 것"이 있다.$A$ 다음 $B$를 해야 하고, $B$ 다음 $C$를 해야 한다면, $A$-$B$-$C$ 순으로 정렬하는 것이다. 위상 정렬 구현하기(Kahn 알고리즘)Kahn 알고리즘은 위상 정렬의 대표적인 알고리즘이다.진입 차수라는 개념을 사용하는데, 이는 말 그대로 한 정점 $A$에 대해 $A$로 향하는 간선의 수를 의미한다. Kahn 알고리즘은진입 차수가 0인 노드를 큐에 집어넣는다.큐에서 노드를 하나씩 뽑으며 연결된 노드들의 진입 차수를 1 줄인다.큐가 빌 때까지 진행한다.모든 정점을 방문하기 전에 큐가 빈다면 해당 그래프에는 사이클이 존재해..

최소 신장 트리란?신장 트리(스패닝 트리)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다.트리이므로 간선의 수는 (정점의 수 - 1)이며, 사이클은 존재하지 않는다. 신장 트리 중 가중치의 합이 최소인 트리를 최소 신장 트리라고 한다. 최소 신장 트리 구하기크루스칼 알고리즘(Kruskal's Algorithm)크루스칼 알고리즘은 가중치가 가장 작은 간선부터 확인하며 사이클이 생기지 않는 경우 MST에 포함하는 그리디(Greedy)적인 방법이다. 먼저 그래프 내의 모든 간선을 가중치에 대한 오름차순으로 정렬한다.이후 반복문을 돌며 가중치가 작은 가중치부터 MST에 포함 가능한지 여부를 판별하는데, 서로소 집합을 이용하는 방법이 가장 대중적이다.($A$와 $B$가 이미 같은 집합에 있다면, 이미 해당 ..

이분 그래프란?이분 그래프란 그래프의 모든 정점을 두 그룹으로 나누어 같은 그룹끼리 이어지는 간선이 없도록 만들 수 있는 그래프를 의미한다.이렇게 되면 이분 그래프의 모든 간선은 서로 다른 그룹의 정점을 연결하게 된다.  이분 그래프 판별어떤 그래프가 이분 그래프인지 아닌지는 DFS나 BFS를 이용해 판별할 수 있다. 특정 정점 하나를 잡아 A그룹으로 둔다.해당 정점과 이어진 정점들은 B그룹으로 둔다.마찬가지로 B그룹 정점과 이어진 정점들은 다시 A그룹으로 둔다.진행 중 모순이 발생했다면 해당 그래프는 이분 그래프가 아니다. 아래 문제를 한 번 풀어보자.더보기import sysfrom collections import dequeinput = sys.stdin.readlinek = int(input())f..

BFS를 이용한 완전 탐색조건: 모든 간선의 가중치가 동일할 때결과: 한 정점에서 다른 모든 정점까지의 거리구현 방법 / 시간복잡도: 큐 / $O(V+E)$ 간선에 가중치가 없거나 모두 동일한 경우 단순 탐색으로 $O(V+E)$만에 최단 경로를 찾을 수 있다.더보기from collections import dequedistances = [None] * Vqueue = deque([0])distances[0] = 0while queue: target = queue.popleft() for next_target in graph[target]: if distances[next_target] == None: queue.append(next_target) distances..