[Python] 프로그래머스 가장 먼 노드 | BFS | 다익스트라

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

- BFS와 다익스트라 알고리즘 두 가지 풀이 방식으로 해결 (DFS도 가능하나 python은 DFS 효율이 좋지 못 함)

 

자세한 설명은 주석 참고

 

 

작성 코드

BFS 풀이

from collections import deque
def solution(n, edge):
    que = deque()  # BFS를 위한 큐
    graph = [[] for _ in range(n + 1)]  # 인접 리스트
    visited = [0] * (n + 1)  # 방문 표시 & 거리를 저장
    for v1, v2 in edge:
        graph[v1].append(v2)
        graph[v2].append(v1)

    que.append((1, 0))  # 1번 노드, 거리 0
    visited[1] = -1  # 1번 노드 방문 표시
    
    while que:  # BFS
        q = que.popleft()
        for v in graph[q[0]]:
            if not visited[v]:  # v노드에 방문한 적이 없다면(기록된 적이 없다면)
                visited[v] = q[1] + 1  # 거리 + 1
                que.append((v, q[1] + 1))
                
    return visited.count(max(visited))

 

다익스트라 풀이

import heapq  # 우선순위 큐를 위한 힙
INF = int(1e9)  # 무한수

def solution(n, edge):
    graph = [[] for _ in range(n+1)]  # 연결 리스트
    distance = [INF]*(n+1)  # 특정 노드로부터 각 노드의 최소 거리 초기화

    for v1, v2 in edge:  # 연결 리스트 초기화
        graph[v1].append(v2)
        graph[v2].append(v1)
        
    def dijkstra(start):  # 다익스트라 함수
        distance[start] = 0  # 시작 노드 거리 0
        q = [] 
        heapq.heappush(q, (0, start))  # 우선순위 큐 초기화

        while q:  # 큐에 값이 있을 동안
            dist, now = heapq.heappop(q)
            if distance[now] < dist:  # 방문했던 노드라면
                continue
            for i in graph[now]:  # 방문하지 않은 노드의 연결 노드 방문
                cost = dist + 1  # 모든 간선 길이는 1
                if distance[i] > cost:  # 계산한 거리가 더 짧다면
                    distance[i] = cost  # 거리 업데이트
                    heapq.heappush(q, (cost, i))  # 우선순위 큐 삽입

    dijkstra(1)  # 1 노드로부터 각 노드가 떨어진 거리
    return distance.count(max(distance[1:]))

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚