[BOJ] 키 순서 - 2458 (G4)

시간 제한	메모리 제한
1 초	128 MB

문제

N명의 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 정확히 알 수 있는 학생의 수를 구하는 프로그램을 작성하시오.

풀이

그래프 탐색 문제이다. 각 학생에 대해 자신보다 큰 학생과 작은 학생을 모두 탐색할 수 있으면, 그 학생의 키 순서를 알 수 있다.

코드

from collections import defaultdict, deque

N, M = map(int, input().split())

taller = defaultdict(list)
shorter = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    taller[a].append(b)
    shorter[b].append(a)

def bfs(graph, start):
    visited = set()
    q = deque([start])
    while q:
        node = q.popleft()
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                q.append(n)
    return visited

result = 0
for i in range(1, N+1):
    visited_taller = bfs(taller, i)
    visited_shorter = bfs(shorter, i)
    # 앞 뒤의 키를 모두 탐색 가능할 경우
    if len(visited_taller) + len(visited_shorter) == N - 1:
        result += 1

print(result)

시간 복잡도

O(N × (N + M))