17616 등수 찾기 (python)

2. 등수 찾기 (17616) - BFS

문제조건

• 학생 두 명의 점수비교만 주어진다.
• 동점자는 없다.
• 학생 x의 가장 높은 등수와 낮은 등수는 ?

아이디어

• 학생 x보다 큰놈 몇명, 작은놈 몇명만 알면 된다. 누가 더 크고 작냐는 중요하지 않다.
• 가장 높은 등수 : 가장왼쪽에 있음 (작은놈), 가장 낮은 등수 : 가장 오른쪽에 있음 (큰놈) 으로 생각하자. 헷갈려
• 가장 높은 등수 : 1 + 학생x보다 작은 학생수
• 가장 낮은 등수 : 전체학생수 - 학생x보다 높은 학생수

• Bfs 로 풀 수 있단다. wow

코드

from collections import deque

def bfs(x, adj):
	rtn = 0
	q = deque()
	q.append(x)
	visited[x] = True

 # 방문한 횟수가 학생 x보다 작은 학생들 수 또는 큰 학생들 수이다.
	while q:
		v = q.popleft()
		for n in adj[v]:
			if not visited[n]:
				q.append[n]
				visited[n] = True
				rtn += 1


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

higher = [[] for _ in range(N+1)]
lower = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(M):
	A, B = map(int(), input().split())

	# A보다 큰 학생들
	higher[A].append(B)
	# B보다 작은 학생들
	lower[B].append(A)

print(1+bfs(X, lower), N-bfs(X, higher))

#올림피아드초등문제