Py) 프로그래머스 49189

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

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

 

from collections import deque
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    visited = [-1]*(n+1)   # 방문 확인

    # edge에서 a, b를 뽑아내서 그래프 생성
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)

    # 방문 예정 노드 설정, 방문 처리
    deq = deque([1])
    visited[1] = 0

    # deq에 있는 노드들을 하나씩 반복한다
    while deq:
        node = deq.popleft()  #deq에 있는 node를 방문해볼 예정
        for next_node in graph[node]:
            if visited[next_node] == -1:      # 아직 방문하지 않음
                deq.append(next_node)       # 다음 방문예정 큐에 넣음
                visited[next_node] = visited[node] + 1  # 거리를 설정, 현재node+1

    # node
    max_d = max(visited)
    for i in visited:
        if i == max_d:
            answer += 1

    return answer

 

*

from collections import deque

그래프 리스트 생성시 graph = [[]]*(n+1)로 하면 주소값이 복사됨, graph[0],...graph[n-1]이 모두 같은 리스트를 가리킴
각자 다른 주소를 가리키게 하려면 for _ in n 이런 식으로 해야함

bfs