프로그래머스 : 가장 먼 노드

def solution(n, edge):
    adj = [[] for _ in range(n + 1)]
    for v1, v2 in edge:
        adj[v1].append(v2)
        adj[v2].append(v1)
    
    ch = [0 for _ in range(n + 1)]
    ch[1] = 1
    
    queue = [1]
    
    while queue:
        cur = queue.pop(0)
        for dest in adj[cur]:
            if not ch[dest]:
                ch[dest] = ch[cur] + 1
                queue.append(dest)
        
    return ch.count(max(ch))

추천 많은 더 좋은 코드

def solution(n, edge):
    graph =[  [] for _ in range(n + 1) ]
    distances = [ 0 for _ in range(n) ]
    is_visit = [False for _ in range(n)]
    queue = [0]
    is_visit[0] = True
    for (a, b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    while queue:
        i = queue.pop(0)

        for j in graph[i]:
            if is_visit[j] == False:
                is_visit[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1

    distances.sort(reverse=True)
    answer = distances.count(distances[0])

    return answer

접근방식

![]

후기

BFS

• ch 배열은 방문 여부와 떨어진 칸 수
• max로 가장 먼 노드 개수 구하기

프로그래머스 : 순위

def solution(n, results):
    answer = 0
    win_graph = defaultdict(set)    # 이긴 애들
    lose_graph = defaultdict(set)   # 진 애들
    
    for winner,loser in results:        # 결과에서 이기고 진 애들 그래프화
        win_graph[loser].add(winner)
        lose_graph[winner].add(loser)

    for i in range(1,n+1):         
        for winner in win_graph[i]:                    # i한테 진 애들은 i를 이긴 애들한테도 진 것
            lose_graph[winner].update(lose_graph[i])
        for loser in lose_graph[i]:                     # i한테 이긴 애들은 i한테 진 애들한테도 이긴 것
            win_graph[loser].update(win_graph[i])
    
    for i in range(1,n+1):
        if len(win_graph[i]) + len(lose_graph[i]) == n-1:   # i한테 이기고 진 애들 합쳐서 n-1이면 순위가 결정된 것
            answer += 1

    return answer
    

결과:런타임 에러

추천많은 깔끔한 코드

from collections import defaultdict
def solution(n, results):
    answer = 0
    win, lose = defaultdict(set), defaultdict(set)
    for result in results:
            lose[result[1]].add(result[0])
            win[result[0]].add(result[1])

    for i in range(1, n + 1):
        for winner in lose[i]: win[winner].update(win[i])
        for loser in win[i]: lose[loser].update(lose[i])

    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n - 1: answer += 1
    return answer

접근방식

![]

후기

• 선수수(100), 경기결과(4500)이므로 완전 탐색도 가능할듯