📕문제

[Baekjoon] 2458. 키 순서

문제 설명

키가 모두 다른 N명의 학생끼리 M번의 키 비교가 이루어졌다.
이 때 자신의 키가 몇 번째인지 알 수 있는 학생이 총 몇명인지 구하는 문제다.

예를 들어 6명의 학생이 있고 다음과 같이 6번의 키 비교가 이루어졌다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

그림으로 표현해보면 다음과 같다.

4번 학생만 자신의 키가 몇 번째인지 알 수 있으므로 1을 반환한다.

---

📝풀이

아이디어는 다음과 같다.

자신보다 작은 학생의 수 + 큰 학생의 수 = N - 1 이면 키가 몇 번째인지 알 수 있다.
딕셔너리에 키 비교 결과를 저장하고(key: 본인, value: 비교 대상) 이 정보를 이용해 탐색을 진행한다.
A보다 B가 크고, B보다 C가 크면 A보다 C가 크다.(반대도 마찬가지) -> dfs

import sys
read = sys.stdin.readline
from collections import defaultdict

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

bigger = defaultdict(set)
smaller = defaultdict(set)

for _ in range(M):
    x, y = map(int, read().split())
    bigger[x].add(y)
    smaller[y].add(x)

def dfs(i, flag):
    if flag:
        for j in bigger[i]:
            if visited[j] == 0:
                visited[j] = 1
                dfs(j, flag)
    else:
        for j in smaller[i]:
            if visited[j] == 0:
                visited[j] = 1
                dfs(j, flag)

result = 0
for i in range(1, N + 1):
    visited = [0] * (N + 1)
    dfs(i, True)
    dfs(i, False)

    if sum(visited) == N-1:
        result += 1

print(result)

• 비교했을 때 자신보다 큰 학생은 bigger, 작은 학생은 smaller 딕셔너리에 저장한다.
• 비교 가능 여부를 확인하기 위해 N+1크기의 visited 배열을 생성한다.
  N이 아닌 N+1인 이유는 학생 번호가 1, 2, 3... 순으로 주어지기 때문. (편의를 위해)
• 각 방향에 대해 dfs를 진행한다.
  flag=Ture: 자신보다 큰 학생 카운트
  flag=False: 자신보다 작은 학생 카운트
  두 함수를 나누는 것이 시간복잡도 면에선 이득이지만 그냥 하나로 합쳤다.
• 체크한 학생의 수가 N-1명이면 결과값에 1을 더한다.