[프로그래머스] 순위 (Python/파이썬)

<문제 링크>

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

프로그래머스

 

<풀이 전략>

1. 언뜻 보면 위상정렬 같아 보이는데 순위가 확정된 선수들의 순위만 반환해야하므로 위상정렬로는 풀 수 없다.

2. 플로이드-와샬로 푼 사람들도 많았는데 그냥 dfs로 푸는 게 더 간단하다

3. 순위가 확정되어있다는 것은 자신의 위(자신 기준 승자)와 아래 (자신 기준 패자)를 모두 안 다는 것이므로, 승자와 패자 그래프 2개를 만들어서 각각에 대해 dfs를 적용해서 파악된 승자와 패자의 합이 자신을 제외한 전체 인원 수와 같으면 순위가 확정되었다고 볼 수 있다.

 

<정답 코드>

# dfs 함수 선언
def dfs(node, graph, visited):

    visited[node] = 1
    
    for next in graph[node]:

        if visited[next]:
            continue

        visited[next] = 1
        dfs(next, graph, visited)

    # 방문한 노드 (승자 or 패자) 수 반환
    return sum(visited) - 1


def solution(n, results):

    answer = 0

    # 승자, 패자 그래프
    win_graph = [[] for _ in range(n + 1)]
    lose_graph = [[] for _ in range(n + 1)]

    for result in results:
        win, lose = result

        win_graph[win].append(lose)
        lose_graph[lose].append(win)


    # 각 노드에 대해서 dfs로 파악된 승자와 패자 수 구하기
    for i in range(1, n + 1):

        # 자신 밑으로 패자의 수
        visited = [0 for _ in range(n + 1)]
        win_cnt = dfs(i, win_graph, visited)

        # 자신 위로 승자의 수
        visited = [0 for _ in range(n + 1)]
        lose_cnt = dfs(i, lose_graph, visited) 

        # 순서가 확정난 경우 
        if win_cnt + lose_cnt == n - 1:
            answer += 1


    return answer