- 선수 i가
이길 수 있는 사람 수 + 질 수 있는 사람 수 = n−1이면 순위 확정 가능
- 경기 결과를 그래프로 만들고, 정방향은 승리 관계, 역방향은 패배 관계로 저장
- A가 B를 이기고, B가 C를 이기면 → A가 C를 이긴다(전이성)는 것을 이용!
- BFS로 정방향 탐색 → i가 이길 수 있는 선수 수(wins) 계산
- BFS로 역방향 탐색 → i가 질 수 있는 선수 수(loses) 계산
from collections import defaultdict
from collections import deque
def bfs(graph, n):
winorlose = []
# 모든 선수에 대해서 체크
for start in range(1, n + 1):
q = deque()
visited = set()
q.append(start)
visited.add(start)
check = []
while q:
a = q.popleft()
# child : a선수의 자식(정방향 그래프 시 a가 이긴 사람들, 역방향 그래프 시 a가 진 사람들)
child = graph[a]
if len(child) > 0:
for c in child:
if c not in visited:
q.append(c)
visited.add(c)
check.append(c)
winorlose.append(check)
return winorlose
def solution(n, results):
graph = defaultdict(list)
inv_graph = defaultdict(list)
for i in range(len(results)):
a, b = results[i][0], results[i][1]
graph[a].append(b)
inv_graph[b].append(a)
wins = bfs(graph, n) # 각 선수들이 이길 수 있는 사람들 리스트(0~n-1)
loses = bfs(inv_graph, n) # 각 선수들이 진 사람들 리스트(0~n-1)
cnt = 0
for i in range(n):
# i가 진 사람들과 이긴 사람들의 수를 더했을 때 자기 제외한 전체 인원수라면 -> 순위를 확정 가능하므로 카운트
if len(wins[i]) + len(loses[i]) == n - 1:
cnt += 1
return cnt
