프로그래머스

프로그래머스 순위 풀이: 승패 전이 관계를 확정하는 플로이드-워셜

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

직접 주어진 경기 결과뿐 아니라 A가 B를 이기고 B가 C를 이긴다면 A가 C를 이긴다는 전이 관계까지 계산해야 한다. 모든 선수 쌍의 도달 가능성을 갱신한 뒤 각 선수의 순위를 판정해야 하므로 Level 3으로 판단했다.

1. 문제 요약

1번부터 n번까지의 권투 선수와 경기 결과 results가 주어진다. [A, B]는 A 선수가 B 선수를 이겼다는 뜻이다. 일부 경기 결과가 분실되어 있을 때, 모든 선수와의 승패 관계를 알 수 있어 정확한 순위를 확정할 수 있는 선수의 수를 반환한다.

중요한 조건은 다음이다.

  • 선수 수 n은 1 이상 100 이하다.
  • 경기 결과의 수는 1 이상 4,500 이하다.
  • 모든 경기 결과에는 모순이 없다.
  • A가 B를 이기고 B가 C를 이겼다면 A가 C를 이긴 것으로 판단할 수 있다.
  • 정확한 순위를 알려면 다른 모든 n - 1명의 선수와 승패 관계를 알아야 한다.

어떤 선수가 3명에게 이기고 1명에게 졌다면, 총 4명의 다른 선수와의 관계가 확정된 것이다. 전체 선수가 5명일 때 정확한 순위를 계산할 수 있다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그래프 구조와 방문 기록

선수를 그래프의 노드로 보고, 승리 결과를 방향 간선으로 표현한다.

A가 B를 이김: A -> B

win[a][b] = True이면 현재까지 확인한 결과에서 A가 B를 이겼다는 뜻이다. 처음에는 직접 주어진 경기 결과만 표시하지만, 중간 선수를 거치는 승패 관계를 반복해서 갱신한다.

전이 관계와 플로이드-워셜

중간 선수 middle을 기준으로 다음 관계를 확인한다.

player -> middle 이고 middle -> opponent 이면
player -> opponent

이를 모든 middle, player, opponent 조합에 적용하면 직접 경기하지 않은 선수 사이의 승패도 알 수 있다. 예를 들어 1 -> 2, 2 -> 3이 주어졌다면 중간 선수 2를 처리할 때 win[1][2]와 win[2][3]이 모두 참이므로 win[1][3]도 참으로 갱신한다.

단계 알려진 관계 새로 확정되는 관계
입력 1 → 2, 2 → 3 없음
중간 선수 2 확인 1 → 2와 2 → 3 1 → 3

각 middle을 한 번씩 중간 노드로 사용하면 길이가 2 이상인 경로도 같은 방식으로 이어 붙인다.

승패 행렬을 전이 관계로 닫는 과정

정확한 순위를 알 수 있는 선수 player는 다른 모든 선수와의 승패 관계가 확정되어야 한다. 다른 선수 opponent에 대해 다음 둘 중 하나가 반드시 참이어야 한다.

  • win[player][opponent]: player가 opponent를 이김
  • win[opponent][player]: player가 opponent에게 짐

두 경우의 개수를 합한 값이 n - 1이면 player와 모든 다른 선수의 관계를 알고 있으므로 정확한 순위를 정할 수 있다. 반대로 합이 작으면 적어도 한 선수와의 관계가 비어 있어 정확한 순위를 확정할 수 없다.

상태 전이와 경계 처리

  1. n x n 크기의 승패 행렬을 False로 초기화한다.
  2. 직접 주어진 [winner, loser] 결과를 True로 표시한다.
  3. 각 선수를 중간 노드로 사용해 간접 승패 관계를 갱신한다.
  4. 각 선수의 승리 수와 패배 수를 계산한다.
  5. 두 수의 합이 n - 1인 선수의 수를 반환한다.

선수 번호가 1부터 시작하므로 행렬은 n + 1 크기로 만들어 win[1]부터 win[n]을 사용한다. 자기 자신과의 관계는 순위 판정에 포함하지 않으므로 승리·패배를 셀 때 opponent != player인 경우만 확인한다.

오답 접근과 반례

직접 주어진 경기 결과만 세면 간접 승패를 놓칠 수 있다.

n = 3
results = [[1, 2], [2, 3]]

직접 결과만 보면 1번 선수는 2번에게만 이긴 것으로 보이지만, 2번을 거쳐 3번에게도 이긴 것을 알 수 있다. 실제로 1번은 모든 선수와의 관계가 확정되어 정확한 순위를 알 수 있다. 전이 관계를 계산하지 않으면 1번을 정확히 판정하지 못한다.

승리 수만 세거나 패배 수만 세면 안 된다. 선수의 전체 순위를 알려면 자신이 이긴 선수와 자신을 이긴 선수를 모두 합해 다른 선수 전체를 포함하는지 확인해야 한다.

시간·공간 복잡도

플로이드-워셜에서 세 선수를 중첩 순회하므로 시간 복잡도는 O(n^3)이다. 승패 관계 행렬을 저장하는 데 O(n^2) 공간이 필요하다. n이 최대 100이므로 이 방식은 제한 조건 안에서 충분히 사용할 수 있다.

3. 문제 해결 코드 (Python)

승패 행렬에 직접 결과를 기록한 뒤 플로이드-워셜 전이를 수행한다. 이후 각 선수의 행에서 승리 관계를, 열에서 패배 관계를 세어 모든 상대와의 관계가 확정되었는지 확인한다.

def solution(n, results):
    win = [[False] * (n + 1) for _ in range(n + 1)]

    for winner, loser in results:
        win[winner][loser] = True

    for middle in range(1, n + 1):
        for player in range(1, n + 1):
            if not win[player][middle]:
                continue

            for opponent in range(1, n + 1):
                if win[middle][opponent]:
                    win[player][opponent] = True

    answer = 0

    for player in range(1, n + 1):
        known_results = 0

        for opponent in range(1, n + 1):
            if opponent == player:
                continue
            if win[player][opponent] or win[opponent][player]:
                known_results += 1

        if known_results == n - 1:
            answer += 1

    return answer

win[player][opponent]는 player가 opponent를 이긴 경우이고, win[opponent][player]는 player가 opponent에게 진 경우다. 둘 중 하나라도 참이면 두 선수의 상대 관계가 확정된 것이므로 known_results를 증가시킨다.

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 전이 관계·연결 상태를 확인했다.

공식 예제

입력: n = 5
results = [[4,3],[4,2],[3,2],[1,2],[2,5]]
기대 출력: 2
확인 결과: 통과
검증 목적: 2번과 5번 선수의 정확한 순위를 판정하는 공식 예제 확인

추가 검증 1: 선수 한 명

입력: n = 1, results = []
기대 출력: 1
확인 결과: 통과
검증 목적: 비교할 상대가 없는 선수의 순위가 확정되는 경계 확인

추가 검증 2: 모든 승패가 전이되는 체인

입력: n = 3, results = [[1,2],[2,3]]
기대 출력: 3
확인 결과: 통과
검증 목적: 1번이 3번을 이기는 간접 관계까지 확정하는지 확인

추가 검증 3: 연결되지 않은 두 그룹

입력: n = 4, results = [[1,2],[3,4]]
기대 출력: 0
확인 결과: 통과
검증 목적: 다른 그룹 선수와의 관계가 없으면 정확한 순위를 셀 수 없는지 확인

추가 검증 4: 한 선수가 모든 선수에게 승리

입력: n = 4, results = [[1,2],[1,3],[1,4]]
기대 출력: 1
확인 결과: 통과
검증 목적: 모든 선수에게 이긴 1번만 다른 선수와의 관계가 모두 확정되는 경우 확인

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 간접 승패와 순위 미확정 사례를 확인할 수 있다.

assert solution(3, [[1, 2], [2, 3]]) == 3
assert solution(4, [[1, 2], [3, 4]]) == 0

5. 다른 풀이 방식 검색 및 비교

각 선수에서 DFS 또는 BFS를 시작해 이길 수 있는 선수와 질 수 있는 선수를 각각 세는 방식도 가능하다. 선수마다 그래프를 탐색하면 시간 복잡도는 O(n(n + e))가 된다.

플로이드-워셜은 모든 선수 쌍의 전이 관계를 한 번에 행렬에 기록한다. n이 100 이하로 작고 결과 관계를 반복해서 확인해야 하므로, 구현이 일정하고 관계 판정이 명확한 플로이드-워셜을 선택했다.

마무리

순위 문제는 직접 주어진 승패만 세는 것이 아니라 승패의 전이 관계를 확정해야 하는 방향 그래프 문제다. A -> B -> C를 A -> C로 확장한 뒤 각 선수의 승리 수와 패배 수의 합이 n - 1인지 확인하면 정확한 순위를 알 수 있는 선수의 수를 구할 수 있다. 선수 수가 작으므로 플로이드-워셜을 사용해 O(n^3) 시간과 O(n^2) 공간에 해결할 수 있다.

관련 문제

#그래프#프로그래머스#난이도 3