문제 링크 : https://www.acmicpc.net/problem/2278
2278번: 그래프 복원
첫째 줄에 그래프를 복원할 수 있으면 1을, 없으면 0을 출력한다. 복원할 수 있을 때, 다음 m개의 줄에 각 간선을 a, b, c의 형태로 출력한다. 이는 정점 a, b를 연결하는 가중치 c인 간선이 있다는 의
www.acmicpc.net
시도한 사람, 푼 사람이 거의 없다..
평소에 해설을 쉽게 보는 편인데 해설이 없어서 강제로 열심히 풀었다.
백준 문제풀이는 너무 많은 사람이 올려서 쓰지 않을 생각이었지만 혹시 궁금한 사람이 있을 수 있으니..
문제유형 - 그래프 복원
비슷한 문제는 1507번 - 궁금한 민호(https://www.acmicpc.net/problem/1507)가 있다.
두 문제의 핵심은 그래프를 복원하는 것.
플로이드 워셜 알고리즘을 통해 최단거리가 정해진 그래프를 원래 그래프로 복원하라는 문제 유형이다.
플로이드 워셜에서 핵심은
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) 이다.
즉 a -> k -> b 경로가 더 짧을 경우에만 graph[a][b]를 갱신시켜준다.
반대로 생각해보면 graph[a][b] 가 graph[a][k] + graph[k][b] 와 같다면 갱신되었다는 것을 알 수 있다.
그리고 짧은 경우에만 갱신되므로 a -> b / a -> k -> b 중 후자가 최단거리라는 것이다.
그럼 도로를 최소한만 쓰기위해서는 a -> b 의 경로는 필요없다.
이를 각자의 방법으로 표시해주면 된다.
만약 graph[a][b] > graph[a][k] + graph[k][b] 라면 말이 되지 않는다.
플로이드 워셜이 적용되었다면 해당 결과는 나올 수 없다.
만약 graph[a][b] < graph[a][k] + graph[k][b] 라면 a -> k -> b 경로가 있기는 하지만 최단 경로는 아니라는 것이다.
주의 : a == k 이거나 b == k 이면 바로 가는 선분을 뜻하므로 제외시켜야 한다.
해설
입력값으로 주어진 그래프를 그릴 수 있는 최소한의 선을 확정짓고 나머지는 아무거나 채우라는 좀 허접한? 문제이다.
두 정점 사이의 최단거리는 500보다 작거나 같은 자연수이므로 최단거리가 아닌 것은 500으로 전부 채우면 된다.
이 때 필요한 간선의 개수는 M 이고 N 개의 정점을 가진 그래프에서 그릴 수 있는 간선의 최대 개수는 N (N - 1) // 2 이다.
아래 세 가지 경우는 말이 안되어 0을 출력해야 한다
- 무조건 있어야 하는 선의 개수가 M 보다 큰 경우
- 필요한 간선의 개수까지 그려하는 선의 개수(M - 무조건 있어야하는 선의 개수)가 그릴 수 있는 최대의 수(간선의 최대 개수 - 무조건 있어야 하는 선의 개수)가 보다 큰 경우 == 즉 M > 간선의 최대 개수 == M > N(N - 1) // 2
- 또 그래프를 복원하는 과정에서 말이 안되는 경우 (graph[a][b] > graph[a][k] + graph[k][b] 인 경우)
이 외의 경우 가능한데, 이후 점들을 돌면서 선분이 꼭 그려져 있는 경우 해당 선분을 출력하고, 선분이 없는 부분은 개수를 세어가며 출력해주면 된다.
추가 테스트케이스
입력
4 6
1 1 2
2 1
1
출력
1
1 2 1
1 3 1
1 4 500
2 3 500
2 4 1
3 4 1
입력
4 5
1 1 2
2 1
1
출력
1
1 2 1
1 3 1
1 4 500
2 4 1
3 4 1
입력
5 10
3 3 13 8
6 13 5
10 11
8
출력
1
1 2 3
1 3 3
1 4 500
1 5 500
2 3 500
2 4 500
2 5 5
3 4 10
3 5 500
4 5 8
입력
5 6
500 3 500 500
500 500 500
500 500
500
출력
0