Q38. 정확한 순위

문제는 여기 참고

[이코테] 최단 경로 - 정확한 순위 (tistory.com)

[이코테] 최단 경로 - 정확한 순위

 

흠 문제를 읽어봤는디.. 이게 왜 최단경로랑 관련이 있을까..

 

음 일단 확실한건

어떤 노드가 정확한 순위를 가지려면

그 노드로 들어오는 노드 개수(건너 들어오는거 포함) + 그 노드로부터 시작해 방문할 수 있는 노드 개수

가 N-1 이어야 한다.

후자는 간단한 서치로도 알 수 있을거같은데 전자를 어떻게 구하지?

오.. 음 알거같다

 

오 명쾌하게 알았다.

플로이드 워셜 문제다!

노드가 N개 있고 특정 노드 i가 정확한 순위를 가지는지 확인한다고 치자.

[i에 도달할 수 있는 노드 개수] + [i에서 출발해서 도달할 수 있는 노드 개수]가 N-1이면 정확한 순위를 가지는거다.

이때 i에 도달할 수 있는 노드 개수는 플로이드워셜그래프의 i번째 열의 원소 중에 INF가 아닌 개수

i에서 출발해서 도달할 수 있는 노드 개수는 플로이드워셜그래프의 i번째 행의 원소중에 INF가 아닌 개수다.

물론 자기 자신은 빼고 세야될것이다. 아니면 자기 자신도 포함시켜서 세고 합이 N이면 정확한 순위를 가지는걸로 판별하던가.

 

정답지를 보니 맞다!!

플로이드 워셜은 오늘 많이 구현했고 이 문제는 이해하는데 시간이 걸리는거지 구현난이도는 낮으니 구현은 패스~