프로그래머스 Lv.3 | Python | 순위

1. 문제 정보

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

입출력 예 설명

• 2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
• 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

---

3. 접근 기준

이 문제는 직접 경기한 결과만 보는 문제가 아니다. 간접 관계까지 확인해야 한다.

예를 들어:

1이 2를 이김
2가 3을 이김

이면:

1은 3도 이길 수 있음

으로 판단할 수 있다. 따라서 각 선수마다 다음 두 가지를 확인해야 한다.

• 이 선수가 이길 수 있는 선수들
• 이 선수를 이길 수 있는 선수들

이를 위해 그래프를 두 개 만든다.

wins  → 내가 이긴 선수 방향
loses → 나를 이긴 선수 방향

그리고 각 선수마다 BFS를 두 번 수행한다.

---

4. 사용한 패턴 / 알고리즘

그래프

• 경기 결과를 방향 그래프로 표현

BFS

• 간접 승리 관계 탐색
• 간접 패배 관계 탐색

---

5. 핵심 아이디어

핵심은 한 선수 기준으로 관계를 양방향으로 확인하는 것이다.

예를 들어 i번 선수에 대해:

1. wins 그래프를 따라가면 i가 이길 수 있는 선수들을 찾을 수 있다.
2. loses 그래프를 따라가면 i를 이길 수 있는 선수들을 찾을 수 있다.

이 두 개의 개수를 합쳤을 때:

win_cnt + lose_cnt == n - 1

이면, 나머지 모든 선수와의 관계가 확인된 것이므로 순위를 알 수 있다.

---

6. 풀이 코드

from collections import deque

def solution(n, results):
    answer = 0

    # wins[a] = a가 이긴 선수 목록
    wins = [[] for _ in range(n + 1)]

    # loses[b] = b를 이긴 선수 목록
    loses = [[] for _ in range(n + 1)]

    # 경기 결과를 그래프로 저장
    for a, b in results:
        wins[a].append(b)
        loses[b].append(a)

    # 각 선수마다 순위를 확정할 수 있는지 확인
    for i in range(1, n + 1):

        # i가 이길 수 있는 선수 수
        win_cnt = 0
        visited = [False] * (n + 1)
        q = deque([i])

        while q:
            node = q.popleft()
            visited[node] = True

            # 현재 선수가 이긴 선수들을 따라감
            for nxt in wins[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    q.append(nxt)
                    win_cnt += 1

        # i를 이길 수 있는 선수 수
        lose_cnt = 0
        visited = [False] * (n + 1)
        q = deque([i])

        while q:
            node = q.popleft()

            # 현재 선수를 이긴 선수들을 따라감
            for nxt in loses[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    q.append(nxt)
                    lose_cnt += 1

        # 다른 모든 선수와 승패 관계가 확인되면 순위 확정 가능
        if win_cnt + lose_cnt == n - 1:
            answer += 1

    return answer

6-1. 코드 추가 설명

이 문제에서 그래프를 두 개 만드는 이유는 방향이 다르기 때문이다.

wins[a].append(b)

는 다음 의미다.

a가 b를 이겼다

즉, a에서 출발하면 a가 이길 수 있는 선수들을 따라갈 수 있다.

반대로:

loses[b].append(a)

는 다음 의미다.

b를 이긴 선수는 a다

즉, b에서 출발하면 b를 이길 수 있는 선수들을 따라갈 수 있다.

예를 들어 경기 결과가 다음과 같다고 하자.

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

그러면 그래프는 다음처럼 만들어진다.

wins = [[], [2], [5], [2], [3, 2], []]

loses = [[], [], [4, 3, 1], [4], [], [2]]

2번 선수 기준으로 보면:

wins[2] = [5]

2번은 5번을 이길 수 있다.

loses[2] = [4, 3, 1]

2번은 4번, 3번, 1번에게 진다.

따라서 2번 선수는:

이길 수 있는 선수: 5번
질 수 있는 선수: 4번, 3번, 1번

즉, 2번 선수는 나머지 4명과의 관계를 모두 알 수 있다.

win_cnt + lose_cnt = 1 + 3 = 4
n - 1 = 4

따라서 2번 선수의 순위는 확정할 수 있다.

---

7. 핵심 로직 요약

이 문제의 핵심은 각 선수 기준으로 이길 수 있는 선수와 질 수 있는 선수를 모두 찾는 것이다.

• 경기 결과를 방향 그래프로 만든다.
• wins에는 이긴 방향을 저장한다.
• loses에는 진 방향을 반대로 저장한다.
• 각 선수마다 wins 방향으로 BFS를 수행한다.
• 각 선수마다 loses 방향으로 BFS를 수행한다.
• 두 개수를 합쳐 n - 1이면 순위 확정 가능하다.

결국, “승리 방향 탐색 + 패배 방향 탐색 + 전체 관계 확인” 이 흐름이 핵심이다.

---

8. 정리

처음 보면 단순히 승패 수를 세면 될 것처럼 보인다. 하지만 직접 경기 결과만으로는 순위를 알 수 없다.

이 문제에서 중요한 부분은 간접 관계였다.

A가 B를 이기고, B가 C를 이기면
A는 C보다 앞에 있다

이 관계를 그래프로 따라가야 한다.

또 하나 중요한 점은 한 방향만 보면 안 된다는 것이다.

순위를 확정하려면:

내가 이길 수 있는 선수
나를 이길 수 있는 선수

둘 다 알아야 한다.

결국 이 문제는 한 선수와 나머지 모든 선수의 관계를 그래프 탐색으로 확인하는 문제라고 볼 수 있다.