[Programmers][Python][동적계획법, DP] 정수 삼각형- level3

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

그래프 level-3

https://donis-note.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%EB%A8%BC-%EB%85%B8%EB%93%9C-level-3-python-%ED%92%80%EC%9D%B4-248455cfa49d

Donis님 블로그에서 인용하였습니다.

https://donis-note.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%EB%A8%BC-%EB%85%B8%EB%93%9C-level-3-python-%ED%92%80%EC%9D%B4-248455cfa49d
import collections
def solution(n, vertex):
    dists = {i:0 for i in range(1, n+1)}  #(1)  
    edge = collections.defaultdict(list)
    
    for v, u in vertex:                   #(2)
        edge[v].append(u)
        edge[u].append(v)
        
    q = collections.deque(edge[1])        #(3)
    dist = 1 
    while q:                              
        for i in range(len(q)):
            v = q.popleft()
            
            if dists[v] == 0:
                dists[v] = dist
                
                for w in edge[v]:
                    q.append(w)
        dist += 1        
    
    del dists[1]                          #(4)
    
    max_value = max(dists.values())
    
    answer = 0
    for v in dists.values():              #(5)
        if v == max_value:
            answer += 1
        
    return answer

 

BFS로 풀어야 한다는 것은 알았으나, 풀다 풀다 구현에서 막힌것 같아 검색을 하게되었습니다. 

푸는데 2시간 이상 걸리면 검색을 하는게 효율이 좋은것 같습니다.