[프로그래머스] 파이썬 문제풀이 - 가장 먼 노드

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

프로그래머스

첫 풀이

1. 그래프 문제에서는 먼저 간선을 탐색하며 리스트형태로 저장해준다

2. 양방향일때는 양쪽다 넣어주어야한다

3. 

 

from collections import deque
def solution(n, edge):
    answer = 0
    q=deque([1])
    ch=[[] for _ in range(n+1)]
    dis=[-1]*(n+1)
    dis[1]=0
    
    for e in edge:
        ch[e[0]].append(e[1])
        ch[e[1]].append(e[0])
    
    while q:
        tmp=q.popleft()

        for i in ch[tmp]:
            if dis[i]==-1:
                q.append(i)
                dis[i]=dis[tmp]+1
    m=max(dis)
    for d in dis:
        if d==m:
            answer+=1
                
    return answer

 

 

배운 점

그래프 문제 푸는법

1. 노드 정보를 2차원리스트에 추가한다

2. 각 노드의 최단거리 리스트를 만든다

3. 이동할 수 있는 노드를 확인하고 아직 방문 안했으면 큐에 추가한다