백준 2458번 - 키 순서

키 순서 문제 바로 가기

풀이 날짜: 2026-03-18

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int, input().split())
graph = [[INF]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if i == j:
            graph[i][j] = 0

for _ in range(m):
    a,b = map(int, input().split())
    graph[a][b] = 1

for k in range(1,n+1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if graph[a][k] != INF and graph[k][b] != INF:
                graph[a][b] = 1

result = 0
for i in range(1,n+1):
    count = 0
    for j in range(1,n+1):
        if graph[i][j] != INF or graph[j][i] != INF:
            count += 1

    if count == n:
        result += 1
print(result)

접근 방법

이 문제는 단순히 주어진 키 비교 관계만으로는 각 학생의 정확한 순위를 알 수 없고, 간접적인 비교 관계까지 모두 고려해야 한다. 예를 들어 A < B, B < C라면 A < C도 알 수 있어야 한다. 따라서 직접 비교뿐 아니라 이러한 간접 관계까지 모두 반영하여, 각 학생이 모든 학생과의 키 관계를 알 수 있는지를 판단하는 것이 핵심이다. 이를 위해 모든 학생 쌍 간의 관계를 완성하는 방식으로 접근하였다.

그래프 초기화

먼저 학생 간의 관계를 저장하기 위해 2차원 배열 graph를 생성하였다. graph[a][b]는 a가 b보다 작다는 관계를 의미하며, 초기에는 알 수 없는 관계이므로 INF로 설정하였다. 또한 자기 자신과의 관계는 항상 성립하므로, graph[i][i] = 0으로 초기화하였다. 이 과정은 이후 플로이드 워셜을 적용하기 위한 기본적인 준비 단계이다.

입력 관계 반영

입력으로 주어지는 a b는 a가 b보다 작다는 의미이므로, graph[a][b] = 1로 설정하였다. 이때의 값 1은 단순히 “관계가 존재한다”는 의미이며, 실제 거리 값 자체는 중요하지 않다. 이 단계까지는 직접 비교 관계만 반영된 상태이다.

플로이드 워셜을 이용한 관계 전파

핵심 아이디어는 어떤 학생 a가 k보다 작고, k가 b보다 작다면, a는 b보다 작다는 관계도 성립한다는 것이다. 이를 코드로 표현하면 graph[a][k] != INF and graph[k][b] != INF일 때 graph[a][b] = 1로 갱신하는 방식이다. 이 과정을 모든 k, a, b에 대해 반복하면, 직접 비교뿐 아니라 간접 비교까지 포함한 전체 관계가 완성된다.

플로이드 이후 graph의 의미

플로이드 워셜이 끝난 뒤의 graph는 다음과 같은 의미를 가진다. graph[i][j] != INF라면 i가 j보다 작다는 것을 알 수 있고, graph[j][i] != INF라면 i가 j보다 크다는 것을 알 수 있다. 즉 두 학생 사이에 어느 방향으로든 경로가 존재하면, 두 학생의 키 관계를 알 수 있는 상태가 된다.

순위를 알 수 있는 학생 판별하

각 학생 i에 대해, 모든 학생 j와의 관계를 확인한다. 만약 i와 j 사이에 i < j 또는 i > j 중 하나라도 성립하면 두 학생의 키 관계를 알 수 있는 것이다. 이를 코드에서는 graph[i][j] != INF or graph[j][i] != INF로 판단한다. 이렇게 해서 i가 모든 학생 j에 대해 관계를 알 수 있다면, 해당 학생의 정확한 순위를 알 수 있다고 판단한다.

count의 의미와 결과 계산

각 학생 i에 대해 관계를 알 수 있는 학생 수를 count로 세고, 그 값이 n과 같다면(자기 자신 포함), i는 모든 학생과 비교가 가능한 상태이다. 따라서 result를 1 증가시킨다. 이 과정을 모든 학생에 대해 반복하면, 최종적으로 정확한 순위를 알 수 있는 학생의 수를 구할 수 있다.

Vienna sausage