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

jioo·2020년 4월 30일
0

문제

구현코드

from collections import defaultdict


def bfs(graph, start, distances):
    q = [start]
    visited = set([start])

    while len(q) > 0:
        current = q.pop(0)
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)
                distances[neighbor] = distances[current] + 1

def solution(n, edge):
    # 그래프 만들기
    graph = defaultdict(list)

    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])

    # bfs 탐색 (최단 거리를 구해야 하므로)
    distances = [0]*(n+1)
    bfs(graph, 1, distances)

    max_distance = max(distances)
    answer = 0

    for distance in distances:
        if distance == max_distance:
            answer += 1

    return answer

후기 😎😎

  • defaultdict 사용법
    • 딕셔너리를 만드는 dict 클래스의 서브클래스
    • 인자로 주어진 객체의 기본값을 딕셔너리의 초기값으로 지정할 수 있다
list_dict = defaultdict(list)

list_dict['key1']

[]
  • bfs 는 최단 거리를 보장
  • set
    • 집합에 관련된 것을 쉽게 처리하기 위해 만든 자료형이다.

s1 = set([1,2,3])
s1
{1, 2, 3}
s2 = set("Hello")
s2
{'e', 'H', 'l', 'o'}


profile
developer

0개의 댓글