풀이
N명의 학생들에 대해 각각 자신의 키가 몇 번째 순서인지 알아내는 문제다.
즉, N명의 키 순서에 대한 단방향 그래프에서 탐색하고자 하는 정점에서 출발하거나 도착하는 관계(간선) 에 대해 자신을 제외한 N - 1 명이 포함 되었는지 살피는 문제다.
가중치는 중요하지 않으니 1로 처리해 단순히 연결 여부만 기록하자.
Floyd Warshall으로 탐색을 진행하며, 단방향 그래프에서 간접적으로 연결된 간선이 존재한다면 두 가중치의 합은 inf가 아니여야 한다.
동일하게 연결 여부만 1로 기록하자.
위의 과정을 진행했다면, 이제는 단방향 그래프속 자신이 갈수 있거나, 자신에게 올 수 있는 정점들의 갯수를 카운트 해야한다.
자기 자신이 아니면서( u != v ), 자신으로부터 갈수있는 정점이 아니고( graph[u][v] == inf ), 자신에게 오지도 않는 정점이 존재한다면( graph[v][u] == inf ) 정확한 키 순서를 알 수 없다.
위의 조건을 모두 통과한 경우에만 자신의 키 순서에 대해 알 수 있을 것이다.
소스코드
출처
2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 28270] Marked-Numbered [Python] (0) | 2023.06.25 |
|---|---|
| [백준 4344] 평균은 넘겠지 [C] (0) | 2023.06.24 |
| [백준 18138] 리유나는 세일러복을 좋아해 [Python] (0) | 2023.06.24 |
| [백준 21612] Boiling Water [Python] (0) | 2023.06.22 |
| [백준 1647] 도시 분할 계획 [Python] (0) | 2023.06.22 |