프로그래머스 그래프 가장 먼 노드 python 풀이

 

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

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

def solution(n:int, edge:int)->int:
    graph =[[] for _ in range(n)]
    distances = [ 0 for _ in range(n) ]
    is_visited = [False for _ in range(n)]
    # 시작 노드 방문
    queue = [0]
    is_visited[0] = True
    # 노드 연결
    for (a,b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    # queue 이용 distance 계산
    while queue:
        i = queue.pop(0)
        # i에서 갈수 있는 j
        for j in graph[i]:
            if is_visited[j] == False:
            	# 갈 수 있으면 앞의 점까지의 거리 + 거리를 1 씩 더한다
                # 시작점의 거리는 0으로 초기화되어 있다.
                is_visited[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1
  
    answer = distances.count(max(distances))
    # max 값의 수를 센다.
    return answer

전형적인 그래프 문제인데... queue를 이용하여 앞의 점부터 1씩 더하면서 나아간다.

마지막에는 최대값의 수를 세어 준다.

queue는 while진입 전 queue 시작점 방문 처리

while 에서 pop후 for에서 방문처리

즉 while 전, for 후에서 방문 처리를 한다는 것을 기억하자