1. 문제 설명

순위

2. 문제 분석

그래프 내 순위를 파악하기 위해서는 '부모 노드 그룹'과 '자식 노드 그룹'을 포함해 다른 모든 노드와 연결되어 있어야 한다.

예를 들어 총 n명이 있을 때 자신을 제외한 n-1 명 중 3명만 자신을 이겼고 나머지 n-4명은 자신보다 순위가 낮다. 이때 이 사람의 순위는 자동으로 4위로 결정된다. 자신이 '직접적으로' 이겼든(즉 직접적인 간선이 있는 상황) '간접적으로' 이겼든 (즉 자신이 그 특정 노드보다 상위 레벨) 연결되어 있어야 한다. 이를 위해 각 노드별로 연결된 노드의 개수를 구해야 한다.

• 부모 노드의 개수 + 자식 노드의 개수 = n-1일 때 이 노드는 순위를 결정할 수 있다.
• 각 연결 관계를 구하기 위해 DFS를 통해 노드 별로 visited된 수만 카운트하자.

3. 나의 풀이

def solution(n, results):
    nodes = [[] for _ in range(n+1)]
    nodes2 = [[] for _ in range(n+1)]
    for tail, head in results:
        nodes[tail].append(head)
        nodes2[head].append(tail)
    # tail -> head 정보 (자식 노드 개수 파악)
    # head -> tail 정보 (부모 노드 개수 파악)

    connected = [0] + [-2]*n
    # 부모 노드, 자식 노드 개수를 DFS로 구할 때 자기 자신을 빼주기 위해 -2

    # 각 노드에서 "연결된" 모든 노드를 visted를 리셋해가면서 카운트 -> 자식 노드, 부모 노드의 개수를 connected에 기록
    for idx in range(1, n+1):
        stack = [idx]
        visited = [False] + [False] * n
        visited[idx] = True
        while stack:
            cur_idx = stack.pop(-1)
            connected[idx] += 1
            for next_idx in nodes[cur_idx]:
                if not visited[next_idx]:
                    stack.append(next_idx)
                    visited[next_idx] = True

    for idx in range(1, n+1):
        stack = [idx]
        visited = [False] + [False] * n
        visited[idx] = True
        while stack:
            cur_idx = stack.pop(-1)
            connected[idx] += 1
            for next_idx in nodes2[cur_idx]:
                if not visited[next_idx]:
                    stack.append(next_idx)
                    visited[next_idx] = True
    
    # 그래프 내 자신의 순위 파악: 부모 노드 + 자식 노드 = n-1개
    # 즉 그래프 내 모든 노드와 연결될 때 순위 파악 가능
    return connected.count(n-1)