[백준] 1719 택배 c++

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

1719번: 택배

 

풀이과정

예전에 다익스트라 + 플로이드 와샬 문제를 푼 적이 있어서 비슷할 거라고 생각했다.  
그러나 생각해야될 것이 많아서 시간이 오래 걸린 문제였다..!

처음에 풀었던 방식은 경유지를 지나면 res배열에 담아주는 방식이다. (2번째 코드)  
그러나 이렇게 되면 1행 6열은 1 -> 2 -> 5 -> 6 두개의 경유지를 거치게 되어  
첫번째 경유지 2가 아닌, 두번째 경유지인 5를 출력하게 되었다.

 

 

최초로 거치는 노드를 출력하기 위해서 방법을 바꿨다.

i에서 j로 갈 때, i에서 k를 거쳐서 j로 가는 것이 더 짧은 경로라면

i에서 k를 가는데 최초로 거치는 노드가 i에서 j로 가는데의 최초로 거치는 노드가 된다.

 

k = 5  
i = 1  
j = 6

1 -> 2 -> 5 -> 6  
res[1][5] = 2;  
res[1][6] = res[1][5] = 2

 

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

int n, m, x, y, z;
int arr[201][201];
int res[201][201];
const int INF = 1e9;

void floyd() {
	for (int k = 1; k <= n; k++) { // 경유지
		for (int i = 1; i <= n; i++) { // 출발지
			for (int j = 1; j <= n; j++) { // 도착지
				if (arr[i][j] > arr[i][k] + arr[k][j]) {
					arr[i][j] = arr[i][k] + arr[k][j];
					// i에서 k를 가는데 최초로 거치는 노드가 i에서 j로 가는데의
					// 최초로 거치는 노드가 된다.
					if (i != k) res[i][j] = res[i][k];
				}
			}
		}
	}
}

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

	cin >> n >> m;
	// 플로이드 와샬 초기 설정
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j) arr[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		arr[x][y] = arr[y][x] = z; // 양방향 간선
		res[x][y] = y; // res[출발지점][도착지점] = 도착지점
		res[y][x] = x;
	}
	floyd();

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

 

=> 아래 코드처럼 풀면 1행 6열이 5가 나온다. (틀린 코드)

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

int n, m, x, y, z;
int arr[201][201];
char res[201][201];
const int INF = 1e9;

void floyd() {
   for (int k = 1; k <= n; k++) { // 경유지
      for (int i = 1; i <= n; i++) { // 출발지
         for (int j = 1; j <= n; j++) { // 도착지
            if (arr[i][j] > arr[i][k] + arr[k][j]) {
               arr[i][j] = arr[i][k] + arr[k][j];
               res[i][j] = k;
            }
         }
      }
   }
   for (int k = 1; k <= n; k++) { // 경유지
      for (int i = 1; i <= n; i++) { // 출발지
         for (int j = 1; j <= n; j++) { // 도착지
            if (i == j) res[i][j] = '-';
            if (i != j && !res[i][j]) {
               res[i][j] = j;
            }
         }
      }
   }
}

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

   cin >> n >> m;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
         if (i != j) arr[i][j] = INF;
      }
   }
   for (int i = 0; i < m; i++) {
      cin >> x >> y >> z;
      arr[x][y] = z;
      arr[y][x] = z;
   }
   floyd();

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