[백준] 등수 찾기

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

17616번: 등수 찾기

그래프 탐색 문제입니다. 이 문제의 특징은 그래프를 2개를 만들어서 각각 그래프를 탐색해야한다는 것 입니다. 자기보다 잘한 사람들을 가르키고 있는 그래프(in_graph)와 자기보다 못한 사람(out_graph)을 가르키고 있는 그래프를 각각 만들고 X보다 잘한 사람을 찾기 위해 in_graph를 탐색하면 자기보다 등수가 높을 수 있는 사람의 수와 out_graph를 탐색하면 자기보다 등수가 낮을 수 있는 사람의 수가 나오게 되고 이를 통해 최대 등수와 최소 등수를 찾을 수 있습니다.

 

저는 BFS로 탐색했는 DFS로 탐색하면 조금 더 짧은 시간에 해결이 가능합니다.

 

import sys
from collections import defaultdict, deque

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline


in_graph = defaultdict(list)
out_graph = defaultdict(list)

# n: 학생의 수, m: 관계의 수, x: 등수를 알고자하는 학생
n, m, x = tuple(map(int, input().split()))

for _ in range(m):  
    high, low = tuple(map(int, input().split()))

    # 자기보다 잘한 학생을 가르킨다.
    in_graph[low].append(high)
    # 자기보다 못한 학생을 가르킨다.
    out_graph[high].append(low)

def bfs(start, graph):
    visited = [False] * (n + 1)
    visited[start] = True

    q = deque([start])
    cnt = -1
    while q:
        cur = q.popleft()
        cnt += 1

        for next in graph[cur]:
            if not visited[next]:
                visited[next] = True
                q.append(next)

    return cnt

# 잘한 사람을 가르키고 있는 그래프를 탐색하면서 x보다 잘한 사람들을 센다
maxRank = 1 + bfs(x, in_graph)
# 못한 사람을 가르키고 있는 그래프를 탐색하면서 x보다 못한 사람들을 센다.
minRank = n - bfs(x, out_graph)

print(maxRank, minRank)