1507. 궁금한 민호

골3 문제로 재활 중이다. 언제까지 재활만 하냐고요? 저도 몰라요..

1507번: 궁금한 민호

---

두 가지 방법으로 풀 수 있는 문제이다.

그리디

주어지는 간선을 비용이 낮은 순서대로 정렬한다. 이때 간선에 방향이 없으므로 $(i, j)~ (i < j)$를 잇는 간선만 담는다.

 

빈 그래프 $graph$를 준비하고, 정렬된 각 간선에 대해 다음을 수행한다.

1. 변수 선언: 이 간선은 정점 $i$와 $j$를 연결하며, 간선의 거리는 $cost$이다.
2. $i$와 $j$가 연결되지 않았거나, $i$와 $j$ 사이의 거리가 $cost$보다 크거나 같다면 $graph$에서 $i$와 $j$를 연결한다.
   • $i$와 $j$ 사이의 거리를 구하는 방법은 여러 가지가 있다. 구현한 방법이 거리를 정확히 구하는 지 반드시 확인하자.
3. 위의 과정을 모든 간선에 대해 수행한다. 중요하다!

이제 주어진 입력과 $graph$를 비교해 보자. 입력에서 주어진 거리와 $graph$에서의 거리가 하나라도 다르다면 ``-1``을 출력해야 한다. 그렇지 않다면 위의 2번 과정에서 연결한 간선의 거리의 합을 출력하면 된다.

플로이드-와샬

사실 난 그리디로만 풀었는데, 플로이드 와샬을 기반으로 풀 수도 있다.

 

핵심 아이디어는 $i$와 $j$, $j$와 $k$가 연결되어 있는데 $dist[i][j] <= dist[i][k] + dist[k][j]~(i \ne j \ne k)$라면 $(i,j)$와 $(j,k)$를 잇는 간선은 필요가 없다는 것이다. 이 방법으로는 풀지 않아서 세부적인 구현은 생략하겠다. 한번 생각해 보길.

---

그냥저냥 무난한 문제. 딱 재활하기 좋은듯?