반응형
풀이
두 개의 리스트를 사용하여 그래프를 저장하고 두 번의 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)
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
2251. 물통 (Python) (0) | 2022.06.16 |
---|---|
17612. 쇼핑몰 (Python) (0) | 2022.06.14 |
4811. 알약 (Python) (0) | 2022.06.13 |
2624. 동전 바꿔주기 (Python) (0) | 2022.06.11 |
1774. 우주신과의 교감 (Python) (0) | 2022.06.10 |
댓글