알고리즘 공부/C++

[G4] 백준 11404번 플로이드 C++ 플로이드 와샬, 최단 경로

마달랭 2024. 10. 4. 16:29
반응형

리뷰

 

노드의 개수가 적을 경우 고려할 수 있는 최단 경로를 구하는 방법인 플로이드 와샬을 사용하는 문제

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

 

전역 변수

  • MAX_D : 거리의 최대값 보다 크게 설정해줄 정수형 상수 변수, 10만 * 10만 이상으로 초기화 해주면 된다.
  • n, m : 노드의 개수 n, 간선의 개수 m
  • lst : 인접 리스트를 행렬으로 변환할 정수형 2차 배열, 행, 열을 노드의 최대 개수인 100보다 크게 설정해 준다.
  • path : 인접 리스트를 저장할 벡터, 다음 노드, 간선 두개를 모두 저장해야 한다.
  • dist : 특정 노드끼리의 거리를 저장할 정수형 2차 벡터

 

함수

1. input

void input()

 

노드와 간선의 개수를 입력 받고 인접리스트와 인접 행렬을 초기화 해주는 함수

 

2. solution

void solution()

 

인접 행렬을 기준으로 거리 벡터를 초기화 해주고, 플로이드 와샬을 통해 각 노드간 거리를 구해주는 함수

각 노드간의 최단 경로를 구해주고 난 뒤 전체 거리 정보를 출력해 준다.

 

문제풀이

  1. input함수를 통해 n, m값을 입력 받는다.
  2. path벡터를 n + 1사이즈로 초기화 해준다.
  3. m개의 간선정보를 받고 path벡터에 단방향 그래프로 추가해 준다.
  4. 각 노드에서 자신에서 출발하는 간선의 정보를 통해 인접 행렬을 lst에 초기화 해준다.
  5. solution함수를 실행하고 dist배열을 n + 1 * n + 1크기로, 값은 최대한 큰 값으로 초기화 해준다.
  6. 인접 행렬에서 각 노드간의 기본 거리를 dist배열에 붙여넣어 준다.
  7. 이후 플로이드 와샬을 통해 각 노드간의 거리를 갱신해 준다.
  8. 갱신작업이 마친 후 거리 정보를 출력해 준다 이때 이동이 불가하거나 자기자신인 경우 거리를 0으로 출력해 준다.

 

참고 사항

비용의 최대는 10만, 간선의 개수는 10만개이므로 정수 타입을 long long로 설정해 주었다.

플로이드 와샬 알고리즘을 사용할 때는 인접 행렬이 가장 적합한 자료구조 이므로 인접 리스트에서 행렬로 바꿔주었다.

 

정답 코드

#include<iostream>
#include<vector>
#define ll long long

using namespace std;
const ll MAX_D = 1e11;
int n, m;
ll lst[101][101];
vector<vector<pair<ll, ll>>> path;
vector<vector<ll>> dist;

void input() {
	cin >> n >> m;
	path.resize(n + 1);
	while (m--) {
		ll a, b, c; cin >> a >> b >> c;
		path[a].push_back({ b, c });
	}

	for (int i = 1; i <= n; i++) {
		for (const auto& val : path[i]) {
			ll j = val.first, w = val.second;
			if (lst[i][j]) lst[i][j] = min(lst[i][j], w);
			else lst[i][j] = w;
		}
	}
}

void solution() {
	dist.resize(n + 1, vector<ll>(n + 1, MAX_D));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (lst[i][j]) dist[i][j] = lst[i][j];
		}
	}

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

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

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

	input();
	solution();
}

 

 

728x90
반응형