[알고리즘][Python] 백준 2458 키 순서 문제 풀이

문제 출처 : www.acmicpc.net/problem/2458

2458번: 키 순서

---

문제 해석 : 키의 대소 비교 결과가 M개 주어졌을 때 N 명의 학생들 가운데 자신의 키 순서를 정확하게 알고있는 사람의 수를 구하는 문제이다.

 

문제 풀이 : 그래프 탐색을 통해서 자신보다 작은 사람의 수, 자신보다 큰 사람의 수를 알고 있는 만큼 기록한다. 이후에 자신이 알고있는 사람의 키 순서가 N-1일때 그 사람은 자신의 키 순서를 정확하게 알고 있다고 볼 수 있다.

 

풀이 시간 (기록용) : 40분

 

---

풀이 코드

from collections import defaultdict, deque

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

order_h = defaultdict(list)
order_l = defaultdict(list)
degree = [0] * (N+1)
for _ in range(M):
    Low, High = map(int, input().split())
    order_h[Low].append(High)
    order_l[High].append(Low)


for key in order_h.keys():
    visited = [0] * (N+1)
    Q = deque()
    Q.append(key)
    visited[key] = 1

    while Q:
        now = Q.popleft()
        if now not in order_h.keys():
            continue
        for element in order_h[now]:
            if visited[element] == 0:
                visited[element] = 1
                degree[element] += 1
                Q.append(element)

for key in order_l.keys():
    visited = [0] * (N+1)
    Q = deque()
    Q.append(key)
    visited[key] = 1

    while Q:
        now = Q.popleft()
        if now not in order_l.keys():
            continue
        for element in order_l[now]:
            if visited[element] == 0:
                visited[element] = 1
                degree[element] += 1
                Q.append(element)

print(degree.count(N-1))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.