일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 가끔은_말로
- 문자열
- 자바스크립트
- 다익스트라
- 미래는_현재와_과거로
- back propagation
- lazy propagation
- 알고리즘
- 세그먼트 트리
- 2023
- pytorch
- tensorflow
- 크루스칼
- 너비 우선 탐색
- object detection
- 플로이드 와샬
- BFS
- dropout
- Overfitting
- 분할 정복
- NEXT
- dfs
- DP
- 우선 순위 큐
- 조합론
- 회고록
- 백트래킹
- c++
- 가끔은 말로
- 이분 탐색
- Today
- Total
Doby's Lab
[알고리즘] 백준 11780번: 플로이드 2 (C++), 최단 경로 발생 노드 담기 본문
https://www.acmicpc.net/problem/11780
이번 문제의 어려운 점은 아마 "i에서 j로 갈 때의 최단 경로에 속한 노드들"을 구하는 것이었다.
[시도 #1]
다익스트라에서 경로 역추적했던 것을 영감 삼아 해결해보려 했었다.
3차원 동적배열을 선언하여 i와 j에 k가 들어가면서 최단 경로가 갱신될 때마다 k를 push 했다.
if (graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
trace[i][j].push_back(k);
}
그리고 출력할 때, i와 j사이에 있는 노드들을 모두 출력해주었다.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) cout << 0 << '\n';
else {
cout << trace[i][j].size() + 2 << ' ';
cout << i << ' ';
for (int k = 0; k < trace[i][j].size(); k++) {
cout << trace[i][j][k] << ' ';
}
cout << j << ' ' << '\n';
}
}
}
사실상 이 코드는 코드의 흐름상 너무 이상하다. (아무래도 생각 없이 구현했던 거 같다.)
i와 j사이에 최단 거리, 노드 k는 하나가 들어있어야 하는데 여러 개를 갱신한다는 게 이상했다.
i와 j 사이에 노드가 2개 이상인 경우는 통하지도 않으며 간혹가다가 4개가 출력되어야 하는데 2~3개가 나오는 오류도 있었다.
[시도 #2]
i와 j 사이의 하나의 노드 k가 들어가는 것을 깨닫고, trace[i][j] = k (노드 i와 j 사이에는 노드 k가 있다는 뜻) 2차원 배열을 만들어 노드들을 담았다.
void floydWarshall() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
trace[i][j] = k;
}
}
}
}
for (int i = 1; i <= n; i++) {
graph[i][i] = 0;
}
}
여기서 또 문제가 있었는데 "이 노드들을 또 어떻게 출력해낼지"가 관건이었다.
[솔루션: 참고했음]
구글링으로 비슷하게 접근한 솔루션들 중 하나를 찾았다. (https://yabmoons.tistory.com/441)
재귀를 통해 출력을 해주었는데 생각해낸 사람 진짜 천재다.
이 함수가 이번 문제의 핵심 포인트다.
void findPath(int start, int end) {
if (trace[start][end] == 0) {
path.push_back(start);
path.push_back(end);
return;
}
findPath(start, trace[start][end]);
path.pop_back(); // end pop: 재귀 2번으로 인해 겹치는 노드 하나 삭제
findPath(trace[start][end], end);
}
다익스트라나 플로이드 와샬에서 start에서 end로 갈 때 최단 경로를 발생시키는 정점들을 알아내는 방법들을 익혀두어야겠다.
다익스트라: 경로 역추적
플로이드 와샬: i,j 사이 노드를 재귀 함수로 구현
[AC 코드]
#include <iostream>
#include <vector>
#include <cmath>
#define MAX 100 + 1
#define INF 987654321
using namespace std;
int n, m;
int graph[MAX][MAX];
int trace[MAX][MAX];
vector<int> path;
void floydWarshall() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
trace[i][j] = k;
}
}
}
}
for (int i = 1; i <= n; i++) {
graph[i][i] = 0;
}
}
void findPath(int start, int end) {
if (trace[start][end] == 0) {
path.push_back(start);
path.push_back(end);
return;
}
findPath(start, trace[start][end]);
path.pop_back(); // end pop: 재귀 2번으로 인해 겹치는 노드 하나 삭제
findPath(trace[start][end], end);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = INF;
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (c < graph[a][b]) {
graph[a][b] = c;
}
}
floydWarshall();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][j] == INF) cout << 0 << ' ';
else cout << graph[i][j] << ' ';
}
cout << '\n';
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][j] == INF || graph[i][j] == 0) cout << 0 << '\n';
else {
path.clear();
findPath(i, j);
cout << path.size() << ' ';
for (int i = 0; i < path.size(); i++) {
cout << path[i] << ' ';
}
cout << '\n';
}
}
}
return 0;
}
무조건 업 솔빙!
'PS > BOJ' 카테고리의 다른 글
[알고리즘] 백준 13424번: 비밀 모임 (C++) (0) | 2021.12.07 |
---|---|
[알고리즘] 백준 2665번: 미로만들기 (C++) (0) | 2021.12.07 |
[알고리즘] 백준 14938번: 서강그라운드 (C++) (0) | 2021.12.06 |
[알고리즘] 백준 2660번: 회장뽑기 (C++) (0) | 2021.12.06 |
[알고리즘] 백준 1613번: 역사 (C++) (0) | 2021.12.06 |