백준 11403 c++ "경로 찾기" -PlusUltraCode-

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

 

 

[필자 사고]

이 문제에서 핵심은 아래와 같다.

1. 갈수 있는 경로가 있으면 무엇이든 상관없다 

2. 모든 경로를 보여주라

즉 플로이드 와샬 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다.

 

이 문제에서 조심해야 될 점은 기존 플로이드 와샬 알고리즘은 sk +ke 값보다 se값이 클경우 값을 갱신해주는 형태이지만

이 문제에서는 갈수 있는 가능성만 알면 되므로 sk 의 값이 1 이고 ke값이 1 인경우 se값도 1 로 바꿔주는 식으로 로직을 작성했다.

 

아래는 소스코드 해설이다.

 

.Input() 함수

• Input() 함수는 먼저 사용자로부터 노드의 개수 N을 입력받는다.
• 그런 다음, 2차원 벡터 arr를 노드의 개수에 맞게 초기화한다. 각 노드에 대한 배열 값은 매우 큰 수인 99999로 초기화되며, 자기 자신으로의 경로는 존재하므로 arr[i][i]는 0으로 설정된다.
• 이후 각 노드 간의 연결 관계를 사용자로부터 입력받아 2차원 배열에 저장한다. 이 배열은 인접 행렬로서, 노드 간의 연결 여부를 나타낸다.
•  
• Floid_Warshall() 함수
• Floid_Warshall() 함수는 플로이드-와샬 알고리즘을 사용하여 모든 노드 쌍에 대한 경로를 계산한다.
• 삼중 반복문을 통해, k번째 노드를 거쳐서 s에서 e로 가는 경로가 존재하는지 확인한다. 만약 s에서 k로 가는 경로(arr[s][k])와 k에서 e로 가는 경로가 모두 존재할 경우, s에서 e로 가는 경로가 존재함을 의미하므로 arr[s][e]를 1로 갱신한다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> arr;

void Input() {
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(N,99999);
		arr[i][i] = 0;
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];
		}
	}
}

void Floid_Warshall() {
	for (int k = 0; k < N; k++) {
		for (int s = 0; s < N; s++) {
			for (int e = 0; e < N; e++) {
				if (arr[s][k] == 1 && arr[k][e])arr[s][e] = 1;
			}
		}
	}
}

void GameStart() {
	Floid_Warshall();

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cout << arr[i][k] << " ";
		}
		cout << '\n';
	}
}

int main(void) {
	Input();
	GameStart();
}