1719 택배

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

1719번: 택배

N이 작고, 시간 제한이 작기 때문에 플로이드 와샬 알고리즘으로 시간 내에 수행이 가능하다.

답안의 요구사항이 제일 첫 번째로 경유하는 지점을 출력하는 것이므로, 최단 거리 갱신을 수행하는 과정에서 시작 지점을 갱신하는 것이 핵심이다.

answer[i][j] = i에서 j로 가기 위한 첫 번째 경유 지점

1. 처음에 입력을 받으면서 시작 지점을 저장한다.

2. 최단거리 갱신 과정에서 경유하는 지점을 기록한다.

 

고찰

첫 번째 시작 지점을 갱신하는 로직을 answer[i][j] = k로 했더니, 틀린 답이 나왔다.

경유하는 지점이 한 개만 있는게 아니기 때문에 틀렸다는걸 알게 되었고, answer[i][j] = answer[i][k]로 수정했다.

플로이드의 최단거리 메커니즘과 유사하게 첫 번째 경유지점을 갱신할 수 있기 때문에 위와 같이 작성하였다.

 

정답코드

#include <iostream>
using namespace std;
#define MAX_SIZE 201
#define INF 987654321
int N, M;
int dist[MAX_SIZE][MAX_SIZE];
int answer[MAX_SIZE][MAX_SIZE];
//최단거리 갱신을 위한 초기화
void setting()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j)
				continue;
			dist[i][j] = INF;
		}
	}
}
void floyd()
{
	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 (dist[i][j] > dist[i][k] + dist[k][j]) {
					answer[i][j] = answer[i][k]; //시작 지점 갱신
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}
}
int main()
{
	cin >> N >> M;
	setting();
	for (int i = 0; i < M; i++) {
		int s, e, d;
		scanf("%d %d %d", &s, &e, &d);
		dist[s][e] = d;
		answer[s][e] = e;
		dist[e][s] = d;
		answer[e][s] = s;
	}
	floyd();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j)
				printf("- ");
			else
				printf("%d ", answer[i][j]);
		}
		printf("\n");
	}
	return 0;
}