문제 설명
•
주어진 경기 결과를 기반으로 각 선수의 순위를 정확하게 결정할 수 있는 선수의 수를 구하는 문제
예제 입력/출력
n | results | return |
5 | [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] | 2 |
제약 조건
•
선수의 수
•
경기 결과
◦
모든 경기 결과에는 모순이 없다.
문제 풀이
•
접근1 플로이드-워셜 -
◦
A가 B를 이기고, B가 C를 이겼다면 A가 C를 이긴 것과 동일하다.
▪
A → B → C 관계가 성립
◦
A가 B에게 졌고, B가 C에게 졌다면 A는 C보다 약하다.
▪
A ← B ← C 관계가 성립
◦
이런 식으로 모든 선수들의 승패 관계를 체크한 뒤, 자신을 제외한 n-1명의 선수와 승패 관계가 모두 확실한 경우, 그 선수의 순위를 정확히 매길 수 있다.
◦
위 과정을 구현하기 위해서, 플로이드-워셜 알고리즘을 활용한다.
▪
모든 선수 (i, j)에 대해 중간 선수(k)를 경유하여 새로운 승패 관계를 유추한다.
•
접근2 집합(set) 연산 -
◦
플로이드-워셜은 모든 관계를 탐색하지만, set 방식은 연결된 선수들만 업데이트한다.
▪
즉, 불필요한 계산을 피할 수 있어 더 빠르게 동작한다.
풀이 코드
•
접근1 플로이드-워셜 -
def solution(n, results):
# 그래프 초기화 (0: 알 수 없음, 1: 승리, -1: 패배)
graph = [[0] * (n + 1) for _ in range(n + 1)]
# 경기 결과 입력
for i, j in results:
graph[i][j] = 1 # 승리
graph[j][i] = -1 # 패배
# 플로이드-워셜 알고리즘
for k in range(1, n + 1): # 경유점
for i in range(1, n + 1): # 출발점
for j in range(1, n + 1): # 도착점
if graph[i][k] == 1 and graph[k][j] == 1: # i -> k -> j 로 이길 수 있음
graph[i][j] = 1
graph[j][i] = -1
elif graph[i][k] == -1 and graph[k][j] == -1: # i -> k -> j 로 질 수 있음
graph[i][j] = -1
graph[j][i] = 1
# 순위 확정 가능한 선수 찾기
answer = 0
for i in range(1, n + 1):
if graph[i][1:].count(0) == 1: # 자신 자신만 0인 경우 (모든 승패 확정)
answer += 1
return answer
Python
복사
•
접근2 집합(set) 연산 -
from collections import defaultdict
def solution(n, results):
win, lose = defaultdict(set), defaultdict(set)
for p1, p2 in results:
win[p1].add(p2)
lose[p2].add(p1)
for p in range(1, n + 1):
for winner in lose[p]: # p가 이긴 모든 상대를 winner도 이길 수 있음
win[winner].update(win[p])
for loser in win[p]: # loser는 p에게 졌으므로, p에게 이긴 선수들에게도 질 것
lose[loser].update(lose[p])
answer = 0
for p in range(1, n + 1):
if len(win[p]) + len(lose[p]) == n - 1:
answer += 1
return answer
Python
복사
