프로그래머스 - 순위

문제 링크 ▶︎ 프로그래머스 순위

문제 전략

이 문제는 DFS 로 푼 문제이다.

우선 딕셔너리 2개 W 와 L 을 만들고, 이긴 상대와 진 상대를 따로 저장한다.
그리고 스택으로 구현한 DFS 함수를 통해서 내가 이길 수 있는 상대와 질 상대를 딕셔너리에 모두 저장한다.

그러면 내가 (이길 수 있는 상대의 수 + 내가 질 수 있는 상대의 수) 의 수가 나를 제외한 전체 인원 수라면 내 순위가 정해지는 것이다.
(이길 수 있는 상대의 수 + 내가 질 수 있는 상대의 수) == 나를 제외한 전체 인원 수 인 player 의 수를 구하면 답이다.

코드

def solution(n, results):
    answer = 0
    w = {i:[] for i in range(1,n+1)}
    l = {i:[] for i in range(1,n+1)}
    for result in results:
        a,b = map(int,result)
        w[a] += [b]
        l[b] += [a]
    
    
    def dfs(k,p):
        visit = [False] * (n+1)
        visit[k] = True
        s = []
        for i in p[k]:
            visit[i] = True
            s.append(i)
        
        while s:
            out = s.pop()
            for x in p[out]:
                if not visit[x]:
                    visit[x] = True
                    p[k] += [x]
                    s.append(x)
        

    for k in range(1,n+1):
        dfs(k,w)
        dfs(k,l)
            
    for player in range(1,n+1):
        if len(w[player]) + len(l[player]) == n-1:
            answer += 1
    
    return answer

개선 사항

dfs 함수를 처음부터 제대로 구현해서 시간 초과나지 않게 주의해야할듯.