문제 요약
n명의 권투 선수가 있다.
경기 결과는 [A, B] 형태로 주어진다.
이는 다음 의미다.
A 선수가 B 선수를 이겼다.권투 실력에는 모순이 없다고 가정한다.
즉, A가 B보다 강하고 B가 C보다 강하다면 A는 C보다 강하다고 볼 수 있다.
목표는 주어진 경기 결과를 바탕으로 정확한 순위를 알 수 있는 선수의 수를 구하는 것이다.
핵심 아이디어
어떤 선수의 정확한 순위를 알 수 있으려면, 그 선수가 다른 모든 선수와 비교 가능해야 한다.
즉, 어떤 선수 i에 대해 다른 선수 j와의 관계가 다음 둘 중 하나로 반드시 알려져 있어야 한다.
i가 j를 이길 수 있다.
j가 i를 이길 수 있다.다른 모든 n - 1명의 선수와 승패 관계를 알 수 있다면, 해당 선수의 순위는 정확히 정해진다.
예시
다음 경기 결과가 있다고 하자.
4 > 3
3 > 2
2 > 5직접 경기 결과는 아니지만 다음 관계를 알 수 있다.
4 > 2
4 > 5
3 > 5이처럼 직접 경기하지 않은 선수들 사이의 승패 관계도 추론해야 한다.
따라서 그래프의 도달 가능성을 구해야 한다.
그래프로 생각하기
선수를 노드로 보고, 승리 관계를 방향 간선으로 표현한다.
A가 B를 이김
=> A -> B그러면 A에서 B로 도달 가능하다는 것은 A가 B보다 강하다는 의미다.
예를 들어 다음과 같은 경로가 있다면,
A -> B -> CA는 B를 이기고, B는 C를 이긴다.
따라서 A는 C보다 강하다고 추론할 수 있다.
A -> C플로이드-워셜 사용하기
선수 수는 최대 100명이다.
n <= 100따라서 모든 선수 쌍의 도달 가능성을 플로이드-워셜로 구할 수 있다.
win[a][b]를 다음과 같이 정의한다.
win[a][b] = True의미는 다음과 같다.
a 선수가 b 선수를 이길 수 있다.초기에는 주어진 경기 결과만 반영한다.
for a, b in results:
win[a][b] = True그다음 중간 선수 mid를 거쳐 갈 수 있는 관계를 갱신한다.
if win[start][mid] and win[mid][end]:
win[start][end] = True즉, start가 mid를 이길 수 있고, mid가 end를 이길 수 있다면 start는 end도 이길 수 있다.
순위를 알 수 있는 선수 판별
모든 승패 관계를 추론한 뒤, 각 선수에 대해 다른 선수들과 비교 가능한지 확인한다.
선수 player와 다른 선수 other에 대해 다음 중 하나라도 참이면 두 선수의 관계를 알 수 있다.
win[player][other]
win[other][player]즉,
player가other를 이길 수 있거나other가player를 이길 수 있으면
두 선수의 순위 관계는 정해진다.
이렇게 비교 가능한 선수가 n - 1명이라면 player의 순위를 정확히 알 수 있다.
전체 코드
def solution(n, results):
win = [
[False] * (n + 1)
for _ in range(n + 1)
]
for winner, loser in results:
win[winner][loser] = True
for mid in range(1, n + 1):
for start in range(1, n + 1):
if not win[start][mid]:
continue
for end in range(1, n + 1):
if win[mid][end]:
win[start][end] = True
answer = 0
for player in range(1, n + 1):
known_count = 0
for other in range(1, n + 1):
if player == other:
continue
if win[player][other] or win[other][player]:
known_count += 1
if known_count == n - 1:
answer += 1
return answer코드 설명
승리 관계 저장
win = [
[False] * (n + 1)
for _ in range(n + 1)
]선수 번호가 1번부터 시작하므로 배열 크기를 n + 1로 만든다.
for winner, loser in results:
win[winner][loser] = True직접 경기 결과를 먼저 저장한다.
관계 추론
for mid in range(1, n + 1):
for start in range(1, n + 1):
if not win[start][mid]:
continue
for end in range(1, n + 1):
if win[mid][end]:
win[start][end] = Truestart -> mid이고 mid -> end라면 start -> end도 가능하다.
이를 모든 중간 선수에 대해 반복하면 간접 승리 관계까지 모두 알 수 있다.
순위 확정 여부 확인
if win[player][other] or win[other][player]:
known_count += 1두 선수 중 누가 더 강한지 알 수 있다면 카운트한다.
if known_count == n - 1:
answer += 1자기 자신을 제외한 모든 선수와 비교 가능하다면 해당 선수의 순위는 정확히 정해진다.
시간 복잡도
플로이드-워셜을 사용하므로 시간 복잡도는 다음과 같다.
O(n^3)제한사항에서 n <= 100이므로 충분히 가능하다.
100^3 = 1,000,000마지막에 각 선수의 순위 확정 여부를 확인하는 데 O(n^2)이 걸린다.
따라서 전체 시간 복잡도는 다음과 같다.
O(n^3)공간 복잡도
승패 관계를 저장하는 2차원 배열을 사용한다.
O(n^2)정리
이 문제는 주어진 경기 결과에서 간접적인 승패 관계를 추론해야 한다.
핵심은 다음과 같다.
A가 B를 이겼다를 방향 그래프로 표현한다.- 플로이드-워셜로 모든 선수 쌍의 승패 관계를 추론한다.
- 어떤 선수가 다른 모든 선수와 비교 가능하면 순위를 정확히 알 수 있다.
정확한 순위를 알 수 있는 조건은 다음 한 줄로 정리할 수 있다.
이길 수 있는 선수 수 + 질 수밖에 없는 선수 수 = n - 1그래프의 도달 가능성을 구하는 문제로 바꾸는 것이 핵심이다.
