다익스트라와 MST(최소신장트리)

 

다익스트라 대표 문제 : https://www.acmicpc.net/problem/1753 (백준 1753 최단경로)

def dijkstra(V, graph, start):
    distance = [float('inf')] * (V + 1)  # 모든 노드의 최단 경로를 무한대로 초기화
    distance[start] = 0  # 시작 노드의 거리는 0으로 설정
    q = [(0, start)]  # (거리, 노드)를 우선순위 큐에 삽입

    while q:
        current_distance, current_node = heapq.heappop(q)

        # 현재 노드까지의 거리가 이미 더 짧다면 무시
        if current_distance > distance[current_node]:
            continue

        # 현재 노드와 연결된 다른 노드들을 확인
        for next_node, weight in graph[current_node]:
            distance_via_current = current_distance + weight

            # 새로운 경로가 기존 경로보다 짧다면 갱신
            if distance_via_current < distance[next_node]:
                distance[next_node] = distance_via_current
                heapq.heappush(q, (distance_via_current, next_node))

    return distance


def main():
    input = sys.stdin.read
    data = input().splitlines()
    
    V, E = map(int, data[0].split())  # V: 정점 개수, E: 간선 개수
    K = int(data[1])  # 시작 노드
    graph = [[] for _ in range(V + 1)]  # 그래프 초기화

    # 간선 정보 입력 받기
    for i in range(2, E + 2):
        u, v, w = map(int, data[i].split())
        graph[u].append((v, w))  # u에서 v로 가는 가중치 w인 간선

    # 다익스트라 알고리즘 수행
    distance = dijkstra(V, graph, K)

    # 결과 출력
    for i in range(1, V + 1):
        if distance[i] == float('inf'):
            print("INF")
        else:
            print(distance[i])

 

MST(최소신장트리) 대표문제: https://school.programmers.co.kr/learn/courses/30/lessons/42861 (프로그래머스 섬 연결하기)

import heapq

def solution(n, costs):
    distance = { node: float('inf') for node in range(n)}
    visited = [False] * n 
    distance[0] = 0 
    q = [(0,0)] # (비용, 시작노드)

    # 그래프를 인접 리스트로 변환
    graph = {i: [] for i in range(n)}
    for u, v, w in costs:
        graph[u].append((v, w))
        graph[v].append((u, w))

    total_cost = 0

    while q:
        curr_cost, curr_node = heapq.heappop(q)
        
        if visited[curr_node]:
            continue

        visited[curr_node] = True
        total_cost += curr_cost

        # 현재 노드에 연결된 다른 노드들 확인
        for next_node, next_cost in graph[curr_node]:
            if not visited[next_node] and next_cost < distance[next_node]:
                distance[next_node] = next_cost
                heapq.heappush(q, (next_cost, next_node))
        
    return total_cost

 

** 방문처리를 하는것과 하지 않는것의 차이 !!!

1. 다익스트라 알고리즘에서의 방문 처리

• 다익스트라 알고리즘은 특정 시작 노드에서 모든 다른 노드로의 최단 경로를 찾는 문제입니다.
• 우선순위 큐를 사용하여 최단 경로가 가장 작은 노드부터 탐색하기 때문에, 큐에서 꺼낼 때 이미 최단 경로가 확정된 상태입니다.
• 따라서, 큐에 중복된 경로가 남아 있더라도, 더 긴 경로는 처리하지 않고 건너뛰므로 방문 처리가 필요하지 않습니다.

2. Prim 알고리즘 (섬 연결하기)에서의 방문 처리

• Prim 알고리즘은 모든 노드를 최소 비용으로 연결하는 **최소 신장 트리(MST)**를 구하는 알고리즘입니다.
• 이 문제에서는 모든 노드를 한 번씩만 방문해야 하며, 중복해서 방문하는 것을 막아야 합니다.
• 방문 처리를 하지 않으면, 이미 연결된 노드를 중복해서 큐에 넣고 다시 처리할 수 있기 때문에 불필요한 작업이 발생할 수 있습니다. 즉, 큐에 중복된 간선이 여러 번 들어가서, 이미 처리된 노드를 다시 방문하는 일이 생길 수 있습니다.
• 따라서 Prim 알고리즘에서는 방문 처리가 필요합니다. 방문한 노드는 다시 큐에 넣지 않도록 방지해야 합니다.

둘의 차이:

• 다익스트라: 큐에서 꺼낸 노드가 이미 최단 경로를 가진 상태이기 때문에, 방문 처리 대신 경로 비교만으로 중복 처리를 방지할 수 있습니다. 즉, 이미 방문한 경로는 더 이상 최단 경로가 될 수 없기 때문에 무시합니다.
• Prim 알고리즘 (섬 연결하기): 모든 노드를 한 번씩만 방문해야 하며, 중복된 간선을 큐에 넣는 것을 방지해야 합니다. 방문 처리 없이 진행하면, 이미 처리된 노드도 다시 큐에 들어가서 계산될 수 있습니다. 최소 신장 트리에서는 모든 노드를 한 번만 연결하는 것이 목적이므로, 방문 처리가 필요합니다.

정리:

• 다익스트라 알고리즘에서는 최단 경로 탐색을 위한 우선순위 큐의 특성 덕분에 방문 처리가 필요하지 않습니다.
• 하지만 Prim 알고리즘에서는 방문 처리가 반드시 필요합니다. 모든 노드를 최소 비용으로 한 번만 연결해야 하기 때문에, 방문한 노드를 다시 처리하지 않도록 관리해야 합니다.

 

 

[ 예시로 설명 ]

 각 노드 간의 연결 비용(가중치)을 사용해 최단 경로를 구하거나, 모든 노드를 최소 비용으로 연결하는 문제입니다.

1. 다익스트라 알고리즘 예시 (최단 경로)

문제:

• A에서 다른 모든 노드로 가는 최단 경로를 구하는 문제입니다.

다익스트라 알고리즘 동작:

1. 초기 상태:
   • 시작점 A에서 모든 노드로 가는 경로는 무한대로 초기화합니다.
   • A에서 시작: A -> B는 1, A -> C는 2.
   • 우선순위 큐 상태: [(1, B), (2, C)]
   • 현재 최단 거리:
     • A -> A: 0
     • A -> B: 1
     • A -> C: 2
     • A -> D: ∞
2. B를 방문:
   • B는 A -> B 경로로 큐에서 꺼내집니다.
   • B와 연결된 C와 D에 대해 경로를 갱신합니다:
     • A -> B -> C는 1 + 3 = 4 (기존 A -> C의 비용 2가 더 짧으므로 무시)
     • A -> B -> D는 1 + 3 = 4로 갱신.
   • 우선순위 큐 상태: [(2, C), (4, D)]
   • 현재 최단 거리:
     • A -> A: 0
     • A -> B: 1
     • A -> C: 2
     • A -> D: 4
3. C를 방문:
   • C는 A -> C 경로로 큐에서 꺼내집니다.
   • C와 연결된 D에 대해 경로를 갱신합니다:
     • A -> C -> D는 2 + 2 = 4 (기존 A -> B -> D의 비용 4와 같으므로 갱신하지 않음).
   • 우선순위 큐 상태: [(4, D)]
   • 현재 최단 거리:
     • A -> A: 0
     • A -> B: 1
     • A -> C: 2
     • A -> D: 4
4. D를 방문:
   • D는 A -> B -> D 또는 A -> C -> D 경로로 큐에서 꺼내집니다. 이미 최단 경로로 갱신된 상태이므로 종료됩니다.

결론:

• A에서 다른 노드로 가는 최단 경로:
  • A -> B: 1
  • A -> C: 2
  • A -> D: 4

방문 처리에 대한 설명 (다익스트라):

• 다익스트라 알고리즘은 우선순위 큐에서 가장 작은 비용의 경로를 먼저 처리합니다.
• 이미 방문된 노드는 더 작은 비용이 나오지 않으므로 별도의 방문 처리 없이 경로 비교만으로 중복된 처리를 방지할 수 있습니다.
• 예를 들어, B -> C 경로가 나중에 큐에 들어오더라도 A -> C 경로가 더 짧았기 때문에 방문 처리 없이 경로를 무시할 수 있습니다.

 

2. Prim 알고리즘 예시 (섬 연결하기 문제)

문제:

• 모든 노드를 최소 비용으로 연결하는 **최소 신장 트리(MST)**를 구하는 문제입니다.

Prim 알고리즘 동작:

1. 초기 상태:
   • 시작점 A에서 연결된 노드를 확인합니다.
   • A와 연결된 B(1)와 C(2)가 있습니다. 비용이 작은 A-B를 선택합니다.
   • 우선순위 큐 상태: [(2, C)]
   • 현재 선택된 간선:
     • A-B (비용 1)
2. B를 방문:
   • B와 연결된 C와 D에 대해 경로를 큐에 추가합니다:
     • B -> C의 비용 3
     • B -> D의 비용 3
   • 우선순위 큐 상태: [(2, C), (3, C), (3, D)]
   • 현재 선택된 간선:
     • A-B (비용 1)
3. C를 방문:
   • C는 A -> C의 경로로 선택됩니다. 비용이 작은 경로를 선택하여 C를 방문합니다.
   • C와 연결된 D를 큐에 추가합니다. C -> D의 비용은 2입니다.
   • 우선순위 큐 상태: [(2, D), (3, D), (3, C)]
   • 현재 선택된 간선:
     • A-B (비용 1)
     • A-C (비용 2)
4. D를 방문:
   • D는 C -> D 경로로 선택됩니다.
   • 모든 노드가 연결되었으므로 종료합니다.
   • 최종 선택된 간선:
     • A-B (비용 1)
     • A-C (비용 2)
     • C-D (비용 2)

결론:

• 최소 비용으로 모든 노드를 연결하는 경로:
  • A -> B, A -> C, C -> D
  • 총 비용: 1 + 2 + 2 = 5

방문 처리에 대한 설명 (Prim):

• Prim 알고리즘은 모든 노드를 한 번씩만 연결해야 합니다. 그러나 큐에 여러 경로가 들어가므로, 이미 연결된 노드를 중복해서 연결할 가능성이 있습니다.
• 예를 들어, B -> C가 큐에 남아 있지만, 이미 A -> C 경로가 선택되었으므로 다시 C를 방문하지 않도록 방문 처리가 필요합니다.
• 만약 방문 처리가 없다면, 이미 연결된 노드를 다시 큐에 넣고 처리하게 되어 불필요한 계산이 발생합니다.

---

결론:

1. 다익스트라 알고리즘은 우선순위 큐에서 경로를 꺼낼 때 최단 경로가 확정되기 때문에 방문 처리가 필요 없습니다.
2. Prim 알고리즘은 최소 비용으로 노드를 연결해야 하는데, 중복 방문을 막기 위해 방문 처리가 필요합니다.

 

 

 

---

 

1. 프로그래머스 가장 먼 노드
https://school.programmers.co.kr/learn/courses/30/lessons/49189

- BFS를 활용한 문제 (다익스트라X)

from collections import deque, defaultdict

def solution(n, edge):
    # 그래프 초기화 (인접 리스트 방식)
    graph = defaultdict(list)
    for u, v in edge:
        graph[u].append(v)
        graph[v].append(u)
    
    # 각 노드의 최단 거리 초기화
    distances = [-1] * (n + 1)
    distances[1] = 0  # 시작 노드 (1번 노드)의 거리 초기화
    
    # BFS 큐 초기화
    queue = deque([1])
    
    # BFS 수행
    while queue:
        node = queue.popleft()
        current_distance = distances[node]
        
        # 인접 노드를 탐색
        for neighbor in graph[node]:
            if distances[neighbor] == -1:  # 미방문 노드
                distances[neighbor] = current_distance + 1
                queue.append(neighbor)
    
    # 최대 거리 계산 및 해당 거리의 노드 개수 세기
    max_distance = max(distances)
    return distances.count(max_distance)

 

 

 

 

2. 프로그래머스 배달

https://school.programmers.co.kr/learn/courses/30/lessons/12978 
다익스트라의 전형적인 문제

- 같은 마을 간의 여러 경로가 존재할 수 있으므로, 더 짧은 경로가 있을 경우 이를 저장하는게 핵심

- 우선순위 큐를 이용해 현재 가장 짧은 거리부터 탐색하며, 이미 저장된 거리보다 짧은 경로가 발견되면 거리를 갱신

import heapq

def solution(N, road, K):
    # 그래프 초기화 (인접 리스트 방식)
    graph = [[] for _ in range(N + 1)]
    for u, v, w in road:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 다익스트라 초기 설정
    distances = [float('inf')] * (N + 1)
    distances[1] = 0
    queue = [(0, 1)]  # (거리, 노드) 형태로 저장
    
    while queue:
        current_dist, node = heapq.heappop(queue)
        # 같은 마을 간의 여러 경로가 존재할 수 있으므로, 더 짧은 경로가 있을 경우 이를 저장
        if current_dist > distances[node]:
            continue
        
        # 인접한 노드 확인 및 거리 갱신
        for neighbor, weight in graph[node]:
            distance = current_dist + weight
            if distance < distances[neighbor]: # 인접노드를 거쳤다 갈때 < 다이렉트로 갈때
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor)) # 인접노드 정보를 heapq에 추가, 과정 반복
    
    # K 이하의 거리로 도달 가능한 마을 개수 세기
    return sum(1 for dist in distances if dist <= K)