[백준 2458번] 키 순서

https://www.acmicpc.net/problem/2458

import sys

input = sys.stdin.readline

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

graph = [[] for _ in range(N+1)]
r_graph = [[] for _ in range(N+1)]

up_count = [0]*(N+1)
down_count = [0]*(N+1)

up_set = [set() for _ in range(N+1)]
down_set = [set() for _ in range(N+1)]

answer = 0

for _ in range(M):
    a, b = map(int,input().split())

    graph[a].append(b)
    r_graph[b].append(a)

def dfs(n,start):

    for index in graph[n]:
        if index not in up_set[start]:
            up_set[start].add(index)
            up_count[start] += 1
            dfs(index,start)

def dfs_r(n,start):

    for index in r_graph[n]:
        if index not in down_set[start]:
            down_set[start].add(index)
            down_count[start] += 1
            dfs_r(index,start)

for i in range(1,N+1):
    dfs(i,i)
    dfs_r(i,i)

for i in range(1,N+1):
    if up_count[i] + down_count[i] == N-1:
        answer += 1

print(answer)

 

이번 문제는 N명의 학생들과 M개의 키 비교가 주어질 때, 자신의 키가 몇 번째로 큰지 알 수 있는 학생들의 수를 구하는 문제이다.

 

본인은 '자신보다 키가 큰 학생의 수와 자신보다 키가 작은 학생의 수를 더한 값이 N-1개인 학생'을 구하는 방식을 떠올렸다.

 

따라서 자신보다 확실하게 키가 큰 학생들을 구하기 위한 그래프(graph)와 자신보다 확실하게 키가 작은 학생들을 구하기 위한 역방향 그래프(r_graph)를 선언한 뒤 DFS 알고리즘을 사용하여 풀이하였다.