[baekjoon] 2278 - 그래프 복원

문제 링크 : https://www.acmicpc.net/problem/2278

2278번: 그래프 복원

시도한 사람, 푼 사람이 거의 없다.. 

평소에 해설을 쉽게 보는 편인데 해설이 없어서 강제로 열심히 풀었다.

백준 문제풀이는 너무 많은 사람이 올려서 쓰지 않을 생각이었지만 혹시 궁금한 사람이 있을 수 있으니..

---

문제유형 - 그래프 복원

비슷한 문제는 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