문제해결 전략

: 플로이드 워셜 + 아이디어...

• 문제에서 단방향인 경우, 양방향으로 만들 수 있도록 카운팅해야 한다고 한다.

핵심!

-> 즉 이미 일반 통행인 길의 경우에만 양방향으로 바꿀수 있는 기회가 주어지는 것이다.

• 우리는 경유지를 통해 모든 정점간의 distT를 구하고 있는 것이므로 플로이드워셜로 진행한다.
• 단방향으로 되어 있는 만약 u->v로 간다고 하면,
  역으로 v->u로 가는 distT을 1로 하면 된다. 설치 비용이라고 생각하면 된다.
  -> k경유지를 거쳐서 진행하면 알아서 갱신된다.

생각해보기

• 아이디어를 만드는 것이 어렵다.
  : 맨 처음에는 distT 만들고, 백트래킹하려고 했는데 굉장히 복잡해질 것이다....

• 양방향인 경우는 distT 값은 0이다.

• 1에서 2로 가는 길이 단방향인 경우 ,
  2에서 1로 가는 경로를 만들어야 한다.
  -> 2개의 정점을 가지고 진행하는 플로이드 워셜이므로 비용을 1로 한다.

• 아래의 입출력을 보면, 2-3-1 즉 양방향이기 때문에
  distT[2][3] 과 distT[3][2] 는 0이다.
  -> 출력문을 통해서도 확인 가능하다.