백준 알고리즘 11404 (플로이드) - C++, Python

[문제] 백준 알고리즘 11404 (플로이드)

> https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

플로이드-와셜 알고리즘을 사용하는 문제이다. ( 시간 복잡도 = O(N^3) )

1~ N의 각 노드에서 출발 했을 때, 다른 노드로 도착하는 최단 거리를 구하는 문제이다.

따라서 N개의 줄을 출력하게 된다.

 

1504번(특정한 최단 경로) + 11657(타임머신)과 비슷한 개념 같다는 생각이 든다.

> https://wlstyql.tistory.com/92 (특정한 최단 경로, 다익스트라 + 중간 노드 개념)

백준 알고리즘 1504 (특정한 최단 경로) - C++, Python

> https://wlstyql.tistory.com/95 (타임머신, 벨만-포드 알고리즘)

백준 알고리즘 11657 (타임머신) - C++, Python

 

[문제 해결]

 

1. graph(N+1 x N+1)에서 시작 노드는 0값으로, 나머지는 INF(1e9)로 초기화한다.

2. 입력을 받으면서 노드의 최소거리를 갱신한다.

3. 시작 노드에서 어느 노드를 거쳐 도착 노드를 가는 반복문을 만들어 준다.

4. 불필요한 반복을 줄이기 위해 시작 노드와 중간 노드가 같을 때는 반복문을 생략한다.

5. 시작 -> 도착 보다 시작 -> 중간 -> 도착 루트가 더 짧다면 갱신한다.

6. graph의 값이 INF일 때는 0, 나머지는 그대로 출력한다.

 

 

[C++]

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 101;
const int INF = 1e9;
int n, m;
int graph[MAX][MAX];

void solve_fw() {
	for (int i = 1; i <= n; i++) {
		for (int v = 1; v <= n; v++) {
			if (v == i) continue;
			for (int nv = 1; nv <= n; nv++) {
				if (graph[v][nv] > graph[v][i] + graph[i][nv]) {
					graph[v][nv] = graph[v][i] + graph[i][nv];
				}
			}
		}
	}
}

void print_graph() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (graph[i][j] == INF) printf("0 ", graph[i][j]);
			else printf("%d ", graph[i][j]);
		}
		printf("\n");
	}
}

void init_graph() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) graph[i][j] = 0;
			else graph[i][j] = INF;
		}
	}
}

int main() {
	scanf("%d", &n);
	scanf("%d", &m);
	init_graph();
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (graph[a][b] > c) graph[a][b] = c;
	}
	solve_fw();
	print_graph();
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[1e9] * (n+1) for _ in range(n+1)]

def init_graph():
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j:
                graph[i][j] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        if graph[a][b] > c:  # 최소거리 갱신
            graph[a][b] = c

def print_graph():
    for i in range(1, n+1):
        for j in range(1, n+1):
            if graph[i][j] == 1e9:
                print("0", end=' ')
            else:
                print(graph[i][j], end=' ')
        print()

def solve_fw():
    for i in range(1, n+1):  # 거쳐갈 노드
        for v in range(1, n+1):  # 시작 노드
            if i == v:  # 불필요한 반복 제거
                continue
            for nv in range(1, n+1):  # 도착 노드
                # 중간 지점을 거쳐간 노드가 더 짧다면 갱신
                if graph[v][nv] > graph[v][i] + graph[i][nv]:
                    graph[v][nv] = graph[v][i] + graph[i][nv]
init_graph()
solve_fw()
print_graph()