https://programmers.co.kr/learn/courses/30/lessons/49191

---

1. 전체 코드

def solution(n, results):
    answer = 0
    graph = [['?'] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                graph[i][j] = '-'
    for i, j in results:
        graph[i][j] = 'win'
        graph[j][i] = 'lose'
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if graph[k][i] == 'win' and graph[j][k] == 'win':
                    graph[j][i] = 'win'
                    graph[i][j] = 'lose'
    for i in graph[1:]:
        if '?' not in i[1:]:
            answer += 1
    return answer
    
   print(solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]))

---

2. 후기

문제를 읽고 그래프 문제라는 생각을 떠올려야한다. 입출력 예시의 results는 그래프 문제에서 자주 나오는 형식의 입력값이며, 특히 선수의 수가 최대 100명이라는 조건은 O(n^3)을 사용하는 플로이드 워셜 알고리즘을 떠올리는 강력한 힌트가 된다. 물론 최단 거리를 구하는 것이 아니기 때문에 정확하게는 플로이드 워셜 알고리즘이라기보다는 3중 for문을 사용한다고 볼 수 있다.

1. 자기 자신을 제외한 모든 선수와 경기를 치뤘다면 정확한 순위를 측정할 수 있다.

2. 승리 조건

주어진 입출력 예시에는 results안에 [4, 2] 값이 들어있지만, 없다고 가정해보자.
선수의 승리 조건은 아래와 같다.

• [3, 2] = 3번 선수가 2번 선수를 이겼다.
• [4, 3] = 4번 선수가 3번 선수를 이겼다.
  -> 4번 선수는 2번 선수도 이겼을 것이다. ([4, 2])

위의 논리를 통해 results에는 없었던 [4, 2]라는 결과값을 승자와 패자에게 모두 기록하는 알고리즘을 만들어야 한다. 코드로 설명하면 아래와 같다.

# k=3
for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
            	# i = 2, j = 4
                if graph[3][2] == 'win' and graph[4][3] == 'win':
                    graph[4][2] = 'win'
                    graph[2][4] = 'lose'

k(=3번)일때, 위의 논리구조를 만족시키는 경우이다.
위와 같은 조건을 확인할 수 있는 이유는 3중 for문을 통해 k(선수), i(선수), j(선수) 세 선수의 모든 논리적 연결관계를 확인할 수 있기 때문이다.

무턱대고 코드로 일반적인 논리관계를 구현하지 않고 [3, 2]와 [4, 3]처럼 예시를 먼저 떠올리고, 코드로 구현했다.

---

• results 값만 입력된 초기값 (문제 입출력 예)

1번 인덱스 = ['-', 'win', '?', '?', '?']
2번 인덱스 = ['lose', '-', 'lose', 'lose', 'win']
3번 인덱스 = ['?', 'win', '-', 'lose', '?']
4번 인덱스 = ['?', 'win', 'win', '-', '?']
5번 인덱스 = ['?', 'lose', '?', '?', '-']

• 결과

['-', 'win', '?', '?', 'win']
['lose', '-', 'lose', 'lose', 'win']
['?', 'win', '-', 'lose', 'win']
['?', 'win', 'win', '-', 'win']
['lose', 'lose', 'lose', 'lose', '-']