2458 키 순서

플로이드 와샬 문제지만, 노드 간의 거리를 굳이 알 필요는 없고 연결 유무만 알면 된다. 플로이드 와샬을 쓰는 이유는 모든 정점에서의 최단 경로를 알 수 있기 때문이다. 플로이드 와샬을 구했다면 어떻게 순서를 알 수 있는 것일까?

1. 어느 한 노드를 잡아본다

2. 나머지 노드간의 관계에서 연결된 노드가 있다면 이 노드는 순서를 알 수 없다

3. 왜냐하면 순서를 명확히 알 수 있다면 자신에서 나가는 노드의 합과 들어오는 노드의 합이 반드시 N-1이어야만 한다

 

문제: https://www.acmicpc.net/problem/2458

깃허브주소: https://github.com/surinoel/boj/blob/master/2458.cpp