[G3] 백준 23286번 허들 넘기 C++ 플로이드 와샬

리뷰

 

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

기본적인 플로이드 와샬 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 정점의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• t : 연습의 횟수를 저장할 변수
• arr : 정점간 가장 높은 허들 높이의 최소값을 저장할 2차원 배열

 

함수

없음

 

 

문제풀이

1. n, m, t값을 입력 받고, n*n크기의 arr배열을 매우 큰 값으로 초기화한다.
2. m개의 단방향 간선 정보를 입력 받아 arr배열에 저장한다.
3. 플로이드 와샬 알고리즘을 통해 i->k, k->j로의 이동이 가능하다면 정점간 가장 높은 허들 높이의 최소값을 arr에 저장한다.
4. t번의 연습을 수행하고, 매 연습마다 변수 f, t에 시작 정점과 도착 정점의 번호를 저장한다.
5. arr[f][t]가 초기값이라면 -1을, 아니라면 arr[f][t]에 저장된 값을 출력 후 개행 문자를 삽입한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 정점의 개수가 적고, 간선의 개수가 많으므로 다익스트라보단 플로이드 와샬 풀이가 더 어울린다.
2. 출발 정점에서 도착 정점으로 가는 경로 중 가장 높은 허들 높이의 최솟값을 출력해야한다.
3. 입력이 1-based-indexing이므로, arr초기화 시 시작 인덱스를 1로 잡아두었다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 301;
int n, m, t;
int arr[N][N];

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

	cin >> n >> m >> t;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			arr[i][j] = 2e9;
		}
	}

	while (m--) {
		int f, t, d; cin >> f >> t >> d;
		arr[f][t] = d;
	}

	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (arr[i][k] == 2e9 || arr[k][j] == 2e9) continue;
				arr[i][j] = min( arr[i][j], max(arr[i][k], arr[k][j]) );
			}
		}
	}

	while (t--) {
		int f, t; cin >> f >> t;
		cout << (arr[f][t] == 2e9 ? -1 : arr[f][t]) << "\n";
	}
}