[S1] 백준 11403번 경로 찾기 C++ 플로이드 와샬, 최단 경로

리뷰

 

플로이드 와샬을 사용해 풀 수 있는 기초적인 문제

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

 

전역 변수

• n : 인접 행렬의 한 변의 길이(노드의 개수)

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 거리를 저장할 2차원 정수 벡터 dist를 n * n크기로 초기화 한다.
2. dist에 인접 행렬을 입력 받아준다, 이때 0이 입력 되었다면 1보다 큰 적절한 수로 변환해 준다.
3. 플로이드 와샬을 통해 3중  for문을 통해 갈 수 있으면서 1보다 큰 간선을 찾아 1로 변경해 준다.
4. 모든 작업을 마친 후 dist벡터 정보를 출력해 준다, 이때 1보다 큰 수라면 0으로 변환해서 출력해 주면 된다.

 

참고 사항

정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

int n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	vector<vector<int>> dist(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> dist[i][j];
			if (!dist[i][j]) dist[i][j] = 100;
		}
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = 1;
				}
			}
		}
	}

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