디너코딩

솔루션

from collections import defaultdict

def solution(n, results):
    answer = 0
    win,lose =defaultdict(set),defaultdict(set)
	# win:key[승리자] values[패배자] / lose:key[패배자] values[승리자]
    for winner,loser in results:
        win[winner].add(loser)
        lose[loser].add(winner)
    
    for i in range(1,n+1):
        # i에게 진 사람은 i를 이긴 사람에게 진다.
        # i에게 이긴 사람은 i에게 진 사람을 이긴다.
        for loser in win[i]:
            lose[loser].update(lose[i])
        for winner in lose[i]:
            win[winner].update(win[i])
    
    # 승패 결과가 본인을 제외한 모든 이와의 경기에서 확정날 경우 순위가 결정
    for i in range(1,n+1):
        if len(win[i])+len(lose[i]) == n-1:
            answer+=1
    
    return answer

너비우선탐색(BFS) 기법을 사용하여 1번 노드에서 각 노드까지의 최단 경로를 계산하여 visited에 딕셔너리 형태로 저장합니다. 그 후 가장 먼 노드의 경로와 같은 값을 갖고 있는 노드를 세서 반환합니다.

솔루션

from collections import defaultdict,deque

def solution(n, edge):
    answer = 0
    graph = defaultdict(list)
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)

    visited= defaultdict(int)
    queue = deque([[1,0]])
    
    # BFS
    while queue:
        current_node,num = queue.popleft()   
        if current_node not in visited:
            visited[current_node] =num
            for adj_node in graph[current_node]: 
                if adj_node not in visited:
                    queue.append([adj_node,num+1])
    # 가장 먼 노드                
    distance = sorted(visited.values(), reverse=True)
    longest = distance[0]
    
    return distance.count(longest)