Data Structure : Graph

Study, Data Structure

Graph 깊이 우선 탐색 너비 우선 탐색 DFS BFS 신장 트리 최소 비용 신장 트리 Kruskal Algorithm 크루스칼 알고리즘 Prime Algorithm 프림 알고리즘 다익스트라 플로이드

Posted Dec 10, 2021

그래프의 구조

그래프란 일정한 규칙 없이 필요에 따라 연결하여 사용하기 위한 비선형 자료구조이다.

버스 노선도나 전철 노선도, 수도 배관에 따른 배수 시스템 등은 선형 자료구조나 트리 자료구조로는 표현할 수 없다.

그래프는 원소 사이의 다:다 관계를 표현하는 비선형 자료구조로, 이런 경우 사용할 수 있는 자료구조가 그래프이다.

그래프는 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합으로 구성된다.

그래프 G는 G=(V,E)로 정의하는데, V는 그래프에 있는 정점의 집합을 뜻하고, E는 정점을 연결하는 간선의 집합을 뜻한다.

그래프 종류

무방향 그래프 (Undirected Graph)
무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프
무방향 그래프에서 정점 V_i와 정점 V_j를 연결하는 간선을 (V_i , V_j)로 표현
무방향 그래프에선 (V_i , V_j)와 (V_j , V_i)는 같은 간선을 나타냄.

방향 그래프 (Directedg Graph)
간선에 방향이 있는 그래프로 다이그래프(Digraph)라고도 함.
정점 V_i와 정점 V_j를 연결하는 간선 즉, V_i -> V_j을 <V_i , V_j>로 표현
V_i를 꼬리, V_j를 머리라고 함.
방향 그래프에선 <V_i , V_j>와 <V_j , V_i>는 서로 다른 간선으로 취급.

완전 그래프 (Complete Graph)
각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프.
정점이 n개인 무방향 그래프에서 최대 간선 수가 n(n-1)/2개
정점이 n개인 향 그래프에서는 두 정점에 대해 방향이 다른 간선을 두 개 연결할 수 있으므로 n(n-1)개

G5는 정점의 개수가 4개인 무방향 그래프이므로 완전 그래프가 되려면 간선이 (4*3)/2 = 6개가 되어야 함.

G6는 정점의 개수가 4개인 방향 그래프이므로 완전 그래프가 되려면 간선이 4*3 = 12개가 되어야 함.

부분 그래프 (Subgraph)
원래 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프.

가중 그래프 (Weight Graph)
정점을 연결하는 간선에 가중치^Weight를 할당한 그래프, 네트워크라고 함.

그래프 관련 용어

간선 (V_i , V_j)가 있을 때 두 정점 V_i , V_j를 인접^Adjacent해 있다고 함.
간선 (V_i , V_j)는 정점 V_i와 V_j에 부속^Incident되어 있다고 함.
무방향 그래프에서는 정점에 부속되어 있는 간선의 수를 차수^Degree라고 함.

무방향 그래프 G1에서 정점 A의 차수는 2, 정점 B의 차수는 3이 됨.

방향 그래프에서는 정점에 부속된 간선 방향에 따라 진입 차수^In-degree와 진출 차수^Out-degree를 구분함.
- 정점을 머리로 하는 간선 수는 진입 차수, 정점을 꼬리로 하는 간선 수는 진출 차수가 됨.
- 정점의 차수는 진입 차수와 진출 차수의 합이 됨.
- 방향 그래프 G3에서 정점 B의 진입 차수는 1, 진출 차수는 2로 정점 B의 차수는 3이 됨.

그래프에서 간선을 따라서 갈 수 있는 길을 순서대로 나열한 것을 경로라고 함.

경로를 구성하는 간선 수는 경로 길이라고 함.

모두 다른 정점으로 구성된 경로를 단순 경로 라고 함.

단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로를 사이클 이라고 함.

방향 그래프이면서 사이클이 없는 그래프를 DAG^{Directed Acylic Graph}라고 함.

그래프에서 두 정점 A, B까지의 경로가 있으면 정점 A, B가 연결되었다고 함.
- 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프를 연결 그래프라고 함. (트리는 사이클이 없는 연결 그래프)
- 연결되지 않은 정점이 있는 그래프는 단절 그래프라고 함.

그래프의 구현

그래프를 구현하려면 정점에 대한 집합과 정점에 부속된 간선의 집합을 표현해야 함.

그래프는 순차 자료구조를 이용하는 2차원 배열의 인접 행렬 방법과 연결 자료구조인 연결 리스트를 사용하는 인접 리스트 방법이 있음.

순차 자료구조를 이용한 그래프 구현

그래프에서는 두 정점을 연결한 간선의 유무를 행렬로 저장하기 위해서 정점 수에 대한 정방 행렬를 사용함.

정점을 n개 가진 그래프는 n X n 정방 행렬을 사용
- 두 정점이 인접되어 있으면 정점을 나태는 행과 열에 대한 행렬값을 1, 인접되어 있지 않으면 행렬값 0

정점을 n개 가진 그래프를 n X n 인접 행렬로 표현하면, 간선 개수에 상관없이 항상 n X n개 메모리를 사용하므로 메모리 낭비 문제가 발생할 수 있음.

연결 자료구조를 이용한 그래프 구현

인접 리스트로 그래프를 표현하는 방법은 각 정점에 인접한 정점들을 단순 연결 리스트로 만드는 것임.

리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성.
어떤 정점의 연결 리스트는 그 정점에 인접한 정점의 수만큼, 즉 그 정점의 차수만큼 노드가 연결되어 있음.
리스트 내의 노드는 저정하는 정점에 대해 오름차순으로 연결.
정점에 대한 인접 리스트의 헤드 포인터는 정점 개수만큼 필요.
각 정점에 대한 헤드 포인터를 그룹으로 묶어서 포인터 배열로 구성.

그래프의 순회(탐색)

그래프 탐색 방법에는 깊이 우선 탐색과 너비 우선 탐색이 있음.

깊이 우선 탐색

깊이 우선 탐색^{DFS: Depth First Search}은 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속하여 결국 모든 정점을 방문하는 순회 방법.
가장 마지막에 만났던 갈림길 간선의 정점으로 되돌아가 다시 DFS를 반복해야 하므로 탐색 과정에서 정점 순서를 관리하기 위해 후입선출 구조의 스택을 사용함.

깊이 우선 탐색 수행 순서를 정리하면 아래와 같음.

각 정점을 방문했는지 여부를 표시하기 위해 배열 visited를 사용, 그래프의 정점 개수를 visited 배열의 크기로 설정 후 모든 배열 요소를 false로 초기화.

정점을 방문하면 해당 정점의 배열 요소값을 true로 설정.

순회과정은 아래와 같다.

1. 그래프 G9의 DFS를 위한 초기 상태 : 배열 visited를 false로 초기화, 공백 스택 생성

2. 정점 A를 시작으로 DFS 시작

3. 정점 A에 방문하지 않은 정점 B,C가 있으므로 A를 스택에 push 후 인접 정점 B와 C 중에서 오름차순에 따라 B를 선택하여 탐색 수행

4. 정점 B에 방문하지 않은 정점 D,E가 있으므로 B를 스택에 push 후 인접 정점 D와 E 중 오름차순에 따라 D를 선택하여 탐색 수행

5. 정점 D에 방문하지 않은 정점 G가 있으므로 D를 스택에 push 후 인접 정점 G를 선택하여 탐색 수행

6. 정점 G에 방문하지 않은 정점 E,F가 있으므로 G를 스택에 push 후 인접 정점 E와 F 중 오름차순에 따라 E를 선택하여 탐색 수행

7. 정점 E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push 후 인접 정점 C를 선택하여 탐색 수행

8. 정점 C에서 방문하지 않은 인접 정점이 없으므로 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은 정점 E에 대해 방문하지 않은 정점이 있는지 확인.

정점 E는 방문하지 않은 인접 정점이 없으므로 다시 pop 수행 후 받은 G에 대해 다시 확인

9. 현재 정점 G에서 방문하지 않은 인접 정점 F가 있으므로 G를 스택에 push 후 인접 정점 F를 선택하여 탐색 수행.

10. 현재 정점 F가 마지막이므로 방문하지 않은 인접 정점이 없으므로 계속해서 pop을 수행하여 A까지 도착하면 스택이 공백이므로 DFS 종료

DFS 순회 경로는 아래와 같음.

너비 우선 탐색

너비 우선 탐색^{BFS: Breadth First Search}은 시작 정점에 인접한 정점을 모두 차례로 방문하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식.
가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 순회 방법.
인접한 정점에 대해 차례로 다시 BFS를 반복해야 하므로 탐색 과정에서 정점 순서를 관리하기 위해 선입선출 구조를 갖는 큐를 사용함.

너비 우선 탐색의 수행 순서를 정리하면 다음과 같음.

너비 우선 탐색도 각 정점을 방문했는지 여부를 표시하기 위해 visited 배열 사용.

순회 과정은 아래와 같음.

1. 초기 상태 : 배열 visited를 false로 초기화, 공백 큐 생성

2. 정점 A를 시작으로 BFS 시작

3. 정점 A에서 방문하지 않은 모든 인접 정점 B,C를 방문하고 큐에 삽입

4. 정점 A에 대한 인접 정점들을 처리한 후 BFS를 계속할 다음 정점을 찾기 위해 큐를 반출하여 B를 받음

5. 정점 B에서 방문하지 않은 모든 인접 정점 D,E를 방문하고 큐이 삽입

6. 정점 B에 대한 인접 정점들을 처리한 후, BFS를 계속할 다음 정점을 찾기 위해 큐를 반출하여 C를 얻음.

7. 정점 C에는 방문하지 않은 인접 정점이 없으므로, BFS를 계속할 다음 정점을 찾기 위해 큐를 반출하여 D를 얻음.

8. 정점 D에서 방문하지 않은 인접 정점 G를 방문하고 큐에 삽입

9. 정점 D에 대한 인접 정점들을 처리한 후, BFS를 계속하기 위한 다음 정점을 찾기 위해 큐를 반출하여 E를 받음.

10. 정점 E에는 방문하지 않은 인접 정점이 없으므로 BFS를 계속하기 위한 다음 정점을 찾기 위해 큐를 반출하여 G를 받음

11. 정점 G에서 방문하지 않은 인접 정점 F를 방문하고 큐에 삽입

12. 정점 G에 대한 인접 정점들을 처리한 후, BFS를 계속하기 위한 다음 정점을 찾기 위해 큐를 반출하여 F를 받음.

13. 정점 F는 모든 인접 정점을 방문하였으므로 큐가 공백 상태이므로 BFS 종료

BFS로 순회한 경로는 아래와 같음.

신장 트리 (Spanning Tree)

트리는 그래프 관점에서 보았을 때 사이클이 없는 그래프임.

모든 정점이 n개인 무방향 그래프 G에서 정점이 n개이고 간선이 n-1개인 트리 형태의 부분 그래프를 신장 트리 라고 함.

그래프에서 순회를 하면 n-1개의 간선을 이동하면서 n개의 모든 정점을 방문하게 되므로 순회 경로는 신장 트리가 됨.

깊이 우선 탐색을 이용하여 생성된 신장 트리를 깊이 우선 신장 트리^{Depth First Spanning Tree}
너비 우선 탐색을 이용하여 생성된 신장 트리를 너비 우선 신장 트리^{Breadth First Spanning Tree}

결국 신장 트리는 간선을 최소로 이용하여 모든 정점을 연결한 그래프임.

최소 비용 신장 트리

가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있음.

무방향 가중치 그래프에서 신장 트리 비용은 신장 트리를 구성하는 간선 n-1개의 가중치를 합한 값이 되는데 이 때 가중치의 합이 최소인 신장 트리를 최소 비용 신장 트리^{Minimum Cost Spanning Tree}라고 함.

최소 비용 신장 트리를 만드는 방법으로 크루스칼^Kruskal이 만든 알고리즘과 프림^Prime이 만든 알고리즘을 주로 이용함.

크루스칼 알고리즘 I

크루스칼 알고리즘 1은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만듦.

» 크루스칼 알고리즘 I의 순서는 아래와 같음. «

그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬.
그래프 G에서 가중치가 가장 높은 간선을 제거. 단, 이때 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 이런 경우에는 그 다음으로 높은 간선을 제거.
그래프 G에 간선이 n-1개만 남을 때까지 2번을 반복.
그래프에 간선이 n-1개만 남으면 최소 비용 신장 트리 완성.

1. 초기 상태 : 간선이 가중치에 따라 내림차순으로 정렬

2. 가중치가 높은 간선 (A,C)를 제거 => 남은 간선 수 10개

3. 남은 간선 중에서 가중치가 가장 높은 간선 (F,G)를 제거 => 남은 간선 수 9개

4. 남은 간선 중에서 가중치가 가장 높은 간선 (B,G)를 제거 => 남은 간선 수 8개

5. 남은 간선 중에서 가중치가 가장 높은 간선 (C,E)를 제거 => 남은 간선 수 7개

6. 남은 간선 중에서 가중치가 가장 높은 간선 (D,E)를 제거하면 그래프가 분리되므로 그 다음으로 높은 (C,F)를 제거해야 하나 이 또한 분리되므로 그 다음으로 높은 (A,D) 제거 => 남은 간선 수 6개

7. 남은 간선 수가 7-1인 6개 이므로 알고리즘을 종료, 신장 트리 완성

크루스칼 알고리즘 II

크루스칼 알고리즘 II는 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만듦.

» 크루스칼 알고리즘 II 순서 «

그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정렬.
그래프 G에 가중치가 가장 낮은 간선 삽입. 단, 이때 사이클을 형성하는 간선은 삽입할 수 없으므로 그 다음으로 가중치가 낮은 간선 삽입.
그래프 G에 간선이 n-1개 삽입될 때까지 2번 반복.
그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리 완성.

1. 그래프의 간선 가중치에 따라 오름차순으로 정렬, 그래프 G는 정점만 있음.

2. 가중치가 가장 낮은 간선 (E,G) 삽입 => 삽입한 간선 수 1개

3. 나머지 간선 중 가중치가 가장 낮은 간선 (A,B) 삽입 => 삽입한 간선 수 2개

4. 나머지 간선 중 가중치가 가장 낮은 간선 (E,F) 삽입 => 삽입한 간선 수 3개

5. 나머지 간선 중 가중치가 가장 낮은 간선 (B,D) 삽입 => 삽입한 간선 수 4개

6. 나머지 간선 중 가중치가 가장 낮은 간선 (A,D) 삽입 시 A-B-D-A의 사이클 생성되므로 삽입 불가하므로 그 다음 낮은 (C,F) 삽입 => 삽입한 간선 수 5개

7. 나머지 간선 중 가중치가 가장 낮은 간선 (D,E) 삽입 => 삽입한 간선 수 6개

8. 현재 삽입한 간선이 6개 이므로 알고리즘 수행 종료, 최소 비용 신장 트리 완성

프림 알고리즘

프림 알고리즘은 크루스칼 알고리즘처럼 미리 간선을 정렬하지 않고, 하나의 정점에서 시작하여 트리를 확장해 나가는 방법.

» 프림 알고리즘 순서 «

그래프 G에서 시작 정점 선택.
선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 연결하여 트리 확장.
이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선 삽입. 단, 사이클을 형성하는 간선은 삽입 불가이므로 이런 경우 그 다음으로 낮은 간선 선택.
그래프 G에 간선이 n-1개 삽입될 때까지 3번 반복.
그래프 G에 간선이 n-1개가 되면 최소 비용 신장 트리 완성.

1. 초기 상태 : 정점 A를 시작 정점으로 선택

2. 정점 A에 부속된 간선 중에서 가중치가 가장 낮은 간선 (A,B)를 삽입하여 트리 확장. => 삽입한 간선 수 1개

3. 현재 확장된 트리의 정점 A,B에 부속된 간선 중에서 가중치가 가장 낮은 간선 (B,D)를 삽입하여 트리 확장. => 삽입한 간선 수 2개

4. 현재 확장된 트리의 정점 A,B,D에 부속된 간선 중 가중치가 가장 낮은 간선인 (A,D)를 삽입하면 A-B-D-A의 사이클이 생성되므로 삽입 불가. 따라서 그 다음으로 낮은 (D,E) 삽입 => 삽입된 간선 수 3개, 삽입 불가한 간선 (A,D)

5. 현재 확장된 트리 A,B,D,E에 부속된 간선 중 가중치가 가장 낮은 간선인 (E,G)를 삽입하여 트리 확장 => 삽입된 간선 수 4개, 삽입 불가 간선 (A,D)

6. 현재 확장된 트리 A,B,D,E,G에 부속된 간선 중 가중치가 가장 낮은 간선인 (E,F)를 삽입하여 트리 확장 => 삽입된 간선 수 5개, 삽입 불가 간선 (A,D)

7. 현재 확장된 트리 A,B,D,E,F,G에 부속된 간선 중 가중치가 가장 낮은 간선인 (C,F)를 삽입하여 트리 확장 => 삽입된 간선 수 6개, 삽입 불가 간선 (A,D)

8. 현재 삽입한 간선 수가 6개이므로 알고리즘 수행 종료, 최소 비용 신장 트리 완성.

최단 경로

최단 경로는 신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치의 합이 최소인 경로.

지하철 노선에서 지정한 출발역에서 목적지까지의 최단 경로를 구하는 지하철 노선 앱이나 길 안내를 하는 내비게이터 등 다양한 서비스에 이용됨.

최단 경로를 구하려는 가중치 그래프의 가중치는 가중치 인접 행렬^{Weight Adjacent Matrix}에 저장함.

가중치 인접 행렬은 그래프에서 사용한 인접 행렬과 같은 형태의 2차원 배열이고, 두 정점 사이에 간선이 없으면 0이 아니라 INF(무한대) 값이 저장되어 있다고 가정.

그리고 각 정점은 자기 자신과 이어진 간선을 허용하지 않으므로 가중치 인접 행렬에서 대각선 값은 0.

최단 경로를 찾는 방법에는 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구하는 다익스트라^Dijkstra 최단 경로 알고리즘과 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 플로이드^Floyd 최단 경로 알고리즘이 있음.

다익스트라 최단 경로 알고리즘

다익스트라는 정점 하나를 출발점으로 두고 다른 모든 정점을 도착점으로 하는 단일점에서의 최단 경로 알고리즘 중 가장 많이 사용됨.
무방향 그래프, 방향 그래프 모두 적용할 수 있음.

기본 원리는 아래와 같음.: 시작 정점 v에서 가장 가까운 정점을 선택하여 추가하면서 추가된 새로운 정점에 의해 단축되는 경로가 있으면, 경로 거리를 수정함.

이 과정을 반복하면서 시작 정점에서 모든 정점에 대한 최단 경로를 구하는 것.

예를 들어 위 그림에서 시작 정점 v에서 정점 u까지의 최단 경로 distance[u] 를 구해 정점 u가 집합 S에 추가되면 새로 추가된 정점 u에 의해 단축되는 경로가 있는지 확인.

즉, 현재 알고 있는 distance[w] 를 새로 추가된 정점 u를 거쳐서 가는 distance[u]+weight[u][w] 를 계산한 경로와 비교해 경로가 단축되면 distance[w] 를 단축된 경로값으로 수정함으로써 최단 경로를 찾는 것.

다익스트라 수행 알고리즘

경로 길이를 저장할 배열 distance 준비

시작 정점으로부터 각 정점에 이르는 경로의 길이를 저장하기 위한 배열 distance를 INF로 초기화

시작 정점 초기화

시작 정점의 distance를 0으로 초기화하고 집합 S에 추가

최단 거리 수정

집합 S에 속하지 않은 정점 중에서 distance가 최소인 정점 u를 찾아 집합 S에 추가.
새로운 정점 u가 추가되면, u에 인접하고 집합 S에 포함되지 않은 정점 w의 distance 값을 다음 식에 따라 수정하고 이 과정을 집합 S에 모든 정점이 추가될 때까지 반복.
distance[w] = min(distance[w], distance[u]+weight[u][w])

다익스트라 알고리즘은 프림 알고리즘과 유사하지만, 프림 알고리즘이 단순히 간선 하나의 길이를 비교하여 선택하는 것과 달리 시작 정점에서부터의 경로 길이를 비교하여 선택함.

» 수행 과정 «

1. 초기 상태 : 시작 정점 A를 집합 S의 초깃값으로 설정, 시작 정점 A에서의 인접 정점에 대한 가중치값을 인접 행렬 weight에서 구해 배열 distance의 초깃값으로 설정.

2. 시작 정점 A의 진출 간선과 연결된 인접 정점 B와 C 중 배열 distance 값이 최소인 정점 C를 집합 S에 추가 후 새로 추가된 정점 C에 의해 단축되는 경로가 있는지 확인하여 배열 distance 값을 업데이트.

정점 B,D,E 업데이트

3. 집합 S에 포함되지 않은 정점 중 배열 distance 값이 최소인 정점 E를 집합 S에 추가 후 정점 E에 의해 단축되는 경로가 있는지 확인하여 distance 배열 업데이트

정점 D 업데이트

4. 집합 S에 포함되지 않은 정점 중에서 배열 distance 값이 최소인 정점 B를 집합 S에 추가 후 정점 B에 의해 단축되는 경로가 있는지 확인하여 업데이트

정점 D 업데이트**

5. 집합 S에 포함되지 않은 정점 중에서 배열 distance 값이 최소인 정점 D를 집합 S에 추가. 모든 정점이 집합 S에 있으므로 A에서 다른 정점으로 가는 최단 경로가 완성됨.

6. 최단 경로 완성 모습

플로이드 최단 경로 알고리즘

플로이드^Floyd 최단 경로 알고리즘은 모든 정점 사이의 최단 경로를 구하는 알고리즘으로 k-최단 경로 라고도 함.

n개의 정점이 있을 때, A^k[v][w]는 k개의 정점을 이용한 정점 v에서 정점 w까지의 최단 경로를 뜻함.
정점 1부터 정점 k-1까지의 정점을 고려한 최단거리 A^k-1을 구한 상태에서 다음 정점 k를 고려할 때, A^k-1[v][w]와 A^k-1[v][k]+A^k-1[k][w] 중에서 작은 값에 따라 최단 경로가 수정됨.
- 즉, A^k[v][w] = min( A^k-1[v][w] , A^k-1[v][k] + A^k-1[k][w] )

플로이드 최단 경로 알고리즘을 정리하면 아래와 같음.

  
Floyd_shortestPath(G,v)
    for (k=1; k<=n; k++)
        for(v=1; v<=n; v++)
            for(w=1; w<=n; w++)
                A[v][w] = min(A[v][w], A[v][k]+A[k][w])
end Floyd_shortestPath()

» 코드로 구현하면 아래와 같음 «

  
#include <iostream>
using namespace std;
int dp[100][100];
const int INF = 1e9;

int main(){
    int N, M; cin >> N >> M;
    for(int i=0; i<N; ++i){
        for(int j=0; j<M; ++j){
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }
    
    //  초기화 : 자기 자신은 0, 나머지는 INF(무한)
    //  입력단계에서 dp[i][j] : i에서 j까지의 거리
    
    for(int i=0; i<M; ++i){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        dp[u][v] = min(dp[u][v], w);
    }

    for(int k=0; k<N; ++k){
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    
    //  dp갱신 후 dp[i][j] : i에서 j까지의 최단거리

    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(dp[i][j] == INF) cout << 0 << ' ';
            else cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }
}

참고

Link: foxtrotin.tistory.com/209?category=635012; foxtrotin.tistory.com/209?category=635012; blog.naver.com/diddnjs02/222000205465