17616. 등수 찾기 (Python)

 

17616번: 등수 찾기

 

풀이

 두 개의 리스트를 사용하여 그래프를 저장하고 두 번의 DFS를 통해서 문제를 해결할 수 있다. 

 

 두 개의 리스트는 각각 자신보다 등수가 높은 학생들의 번호와 자신보다 등수가 낮은 학생들의 번호를 저장한다. 입력에서 주어지는 X번 학생부터 시작하여 DFS를 통해 자신보다 등수가 높은 학생이 총 몇 명있는지를 체크하고 다시 한 번 DFS를 통해 자신보다 등수가 낮은 학생이 총 몇 명 있는지를 체크한 후 이를 통해서 가능한 등수의 범위를 구해준다.

 

코드

import sys
input = sys.stdin.readline

# 자신보다 등수가 높거나 낮은 학생이 몇 명 있는지를 체크하기 위한 DFS 함수
# 처음 num은 X번 학생이고 arr은 각 학생 별로 자신보다 등수가 높은(또는 낮은) 학생의 번호를 저장해 놓은 리스트이다.
def dfs(num, arr):
    cnt = 1

    visited[num] = True
    for nextNum in arr[num]:
        if not visited[nextNum]:
            cnt += dfs(nextNum, arr)

    return cnt


if __name__ == '__main__':
    # N명의 학생, M번의 질문, 등수의 범위를 알고 싶은 학생 번호 X
    N, M, X = map(int, input().split())
    up = [[] for _ in range(N+1)]  # 자신보다 등수가 높은 학생의 정보를 담는 리스트
    down = [[] for _ in range(N+1)]  # 자신보다 등수가 낮은 학생의 정보를 담는 리스트
    visited = [False for _ in range(N + 1)]  # DFS에서 방문 체크를 하기 위한 리스트
    u, v = 1, N  # u: 가능한 가장 높은 등수, v: 가능한 가장 낮은 등수

    for _ in range(M):
        a, b = map(int, input().split())  # a번 학생 > b번 학생
        up[b].append(a)  # up[b]에 b보다 등수가 높은 a번 학생의 정보를 담는다.
        down[a].append(b)  # down[a]에 a보다 등수가 낮은 b번 학생의 정보를 담는다.

    u += dfs(X, up) - 1  # X번보다 등수가 높은 학생의 수를 구한다. 자기 자신까지 포함되므로 최종적으로 -1을 해준다.
    v -= dfs(X, down) - 1  # X번보다 등수가 낮은 학생의 수를 구한다. 자기 자신까지 포함되므로 최종적으로 -1을 해준다.

    print(u, v)