[C++] 백준 11403 : 경로 찾기

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

백준 11403번 경로 찾기를 풀었다.

 

플로이드 와샬 알고리즘을 처음 사용해봤다.

플로이드 와샬 알고리즘은 모든 노드 사이의 최단 경로를 구할 수 있는 알고리즘이다.

2차원 인접 행렬이 주어졌을 때, 삼중 반복문을 사용해서 경로를 계산하기 때문에 시간복잡도는 O(n^3)이다.

인접 행렬의 값을 이용해서 dist배열을 초기화 시킨 후에 반복문을 수행하면 된다.

 

dist[i][j] 는 i 노드에서 출발해서 j 노드에 도착하는 최단 거리이다.

만약 k라는 중간 노드를 거쳐서 가는 경로가 더 짧다면 dist[i][k] + dist[k][j] 값을 최단 거리로 설정한다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

#define INF 1000000
int adj[100][100];
int dist[100][100];


int main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int temp;
			cin >> temp;
			adj[i][j] = temp;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j)
				dist[i][j] = INF;
			else if (adj[i][j] != 0)
				dist[i][j] = adj[i][j];
			else
				dist[i][j] = INF;
		}
	}

	for (int k = 0; k < N; k++) { // Via node
		for (int i = 0; i < N; i++) { // Start node
			for (int j = 0; j < N; j++) { // End node
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

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

	return 0;
}