[프로그래머스] 가장 먼 노드

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

기준 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제였습니다.

다익스트라를 이용하여 가장 멀리 있는 노드의 거리를 구한 이후 해당 거리에 있는 노드의 개수를 확인하였습니다.

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

import heapq

def solution(n, edge):  
    linked = [[] for _ in range(n+1)]               # 노드의 연결 관계
    distance = [0] * (n+1)                          # 노드들의 거리

    for a, b in edge:                               # 노드 연결 관계 정리 (양방향)
        linked[a].append((1, b))
        linked[b].append((1, a))

    def dijkstra(start):                            # 다익스트라
        h = [(1, start)]                            # 시작 노드 입력

        while h:
            node = heapq.heappop(h)
            if not distance[node[1]]:               # 아직 확인 안한 노드이면
                distance[node[1]] = node[0]         # 거리 기록
                for next in linked[node[1]]:        # 다음 노드들 탐색
                    heapq.heappush(h, (node[0]+next[0], next[1]))

    dijkstra(1)
    max_distance = max(distance)                    # 가장 먼 거리 구하기
    answer = distance.count(max_distance)           # 가장 먼 거리에 있는 노드의 개수 세기
    return answer

print(solution(6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]))

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3 

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다