[그래프] 순위

문제

확실히 순위가 정해진 사람의 수를 세야했다.

고민 많이 했다. 고민하다가 아이디어가 생각났다!

결국 순위가 확실하려면 자신을 제외한 모두와 우위를 비교해야한다.

내가 방문할 수 있는 노드 개수 + 방문당한 노드개수 == 전체 노드수 -1

따라서

1. 승패결과에 따라 단방향 그래프를 만든다
2. 각 노드에서 순회해서 visited를 만든다
3. 각 노드별로 visited를 이용해서 승패를 기록한다
4. 승패의 합이 n-1인지 확인한다.

위의 내용을 코드로 구현하다보니 코드가 매우 장황해졌다.. 최선이다...^_ㅠ

구현하며 어려웠던 건 dfs로 순회하려다가 visited가 노드별로 만들어야하는데 global 지정이 꼬였다. 그래서 그냥 깔끔쓰하게 bfs로 바꿨다.

왠만하면 bfs 쓰는걸로!

from collections import deque
            

def make_check(me, visited):
    for i, val in enumerate(visited):
        if i==me:
            continue
        elif val == True:
            check[0][i] += 1
        
    cnt = visited.count(True)
    check[1][me] += cnt-1 
    

def solution(n, results):
    # check
    global check
    check = [[0 for _ in range(n+1)] for _ in range(2)]
    
    # grid
    grid = [[] for _ in range(n+1)]
    for r in results:
        s, e = r[0], r[1]
        grid[s].append(e)
    
    def bfs(s):
        visited = [False for _ in range(n+1)]
        queue = deque([s])
        while queue:
            s = queue.popleft()
            
            if visited[s] == False:
                visited[s] = True

            for next in grid[s]:
                if visited[next] == False:
                    queue.append(next)
        return visited
    
    
    for i in range(1, n+1):
        
        visited = bfs(i)
        make_check(i, visited)
    
    answer = 0
    for i in range(1, n+1):
        if check[0][i] + check[1][i] == n-1:
            answer += 1
    return answer