프로그래머스 [Lv. 3] 순위 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/49191?language=python3

프로그래머스

정답 코드

def solution(n, results):
    answer = 0
    wAdjL = [[] for _ in range(n+1)]
    lAdjL = [[] for _ in range(n+1)]
    for win, lose in results:
        wAdjL[win].append(lose)
        lAdjL[lose].append(win)
    
    n_1 = n - 1
    
    records = [[0, 0] for _ in range(n+1)]
    def dfs(me, adjL, code):
        for who in adjL[me]:
            if visited[who]:
                continue
            records[who][code] += 1
            visited[who] = 1
            dfs(who, adjL, code)
                
    for i in range(1, n+1):
        visited = [0 for _ in range(n+1)]
        dfs(i, wAdjL, 0)
    
    for j in range(1, n+1):
        visited = [0 for _ in range(n+1)]
        dfs(j, lAdjL, 1)
        
    for record in records:
        if sum(record) == n_1:
            answer += 1

    return answer

풀이 방법

1. 자신이 이긴 사람을 포함하는 wAdjL과 자신을 이긴 사람을 포함하는 lAdjL을 만든다.
2. dfs 함수를 만들고 각각의 adjL을 가지고 탐색을 한다.
   1. lAdjL을 사용하는 경우 자신을 이긴 사람들을 탐색해 가면서 records의 j, 1 인덱스를 채운다.
   2. wAdjL을 탐색하면서 records의 i, 0 인덱스를 채운다.
3. 이후 records의 record가 n - 1인 경우
   1. 해당 인물은 모두와 연관이 있으며 이는 등수를 명확히 할 수 있다는 말이 된다.
   2. 이에 answer에 1을 더해준다.
4. answer를 반환하면 끝!

느낀점

• 고민을 좀 하긴 했는데 생각보다 쉽게 풀렸다.