플로이드-워셜1 키 순-서 & 플로이드-워셜 알고리즘 키 순-서 백준 2456번 문제https://www.acmicpc.net/problem/2458 1. 문제 2. 문제 풀이2.1 아이디어자신의 키 순서를 알기 위한 조건은 그래프상 모든 학생들과 연결되어 있어야 한다는 것이다. 예를 들어 5번은 3번과 6번에 연결되어 있지 않다.이 때문에 3번과 6번이 자신과 비교해서 어디에 위치해 있는지 알 수 없기 때문에 순서를 매길 수 없다. [순서를 알 수 없는 경우] 따라서 어떤 학생이 정방향과 역방향을 포함해서 모든 학생들과 연결되어 있으면 그 학생의 키 순서를 알 수 있다. 노드가 연결되어 있다는 것은 노드 간에 경로가 존재한다는 것이다.때문에 모든 노드간 가능한 모든 경로를 탐색하는 플로이드-워셜 알고리즘을 사용해서 이 문제를 해결할 수 있다. .. 2024. 8. 2. 이전 1 다음
