[백준] 1939 : 중량제한 (파이썬)

MST / BFS + 이진탐색 문제

https://www.acmicpc.net/problem/1939

---

최소 신장 트리(MST)란?

개념

connected, weighted, undirected(양방향 가중 그래프)에서 정의되며, 신장 트리 중에서 가중치의 합이 최소가 되는 신장 트리이다.

즉, 그래프에서 모든 정점을 포함하면서, 간선들의 가중치 합이 최소가 되는 트리를 의미한다.

 

최소 신장 트리 (가중치 합 : 8)

 

구현 방식

MST를 구현하기 위해선 두개의 그리디 알고리즘을 사용할 수 있다.

 

1) Prim's Algorithm

• 다엑스트라와 비슷한 방식이다.
  • Dijkstra는 최단 경로를 찾는 알고리즘
  • Prim은 최소 신장 트리를 찾는 알고리즘 (MST)
• 자료구조 heap을 활용하여 최소 신장이 되도록 노드를 방문하는 식으로 구현한다.
  • 트리를 확장해 나가면서, 이미 선택된 노드들로부터 연결된 간선 중에서 가중치가 가장 적은 간선을 선택해 트리에 포함되지 않은 노드를 추가한다. 

1. 시작 정점을 선택하고, 그 정점에서 연결된 모든 간선을 우선순위 큐에 넣는다.
2. 우선순위 큐가 비지 않았고, 트리에 포함된 간선이 n-1개가 되지 않았다면:
    a. 힙에서 가장 작은 가중치를 가진 간선을 선택한다.
    b. 그 간선이 연결하는 두 정점 중 트리에 포함되지 않은 정점을 트리에 추가한다.
    c. 새로 추가된 정점에서 연결된 간선들을 힙에 넣는다.
3. 선택된 간선들로 이루어진 트리가 최소 신장 트리이다.

 

2) Kruskal's Algorithm

• union find 알고리즘을 활용하여 구현한다.

1. 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 각 정점을 개별적인 집합으로 만든다.
3. 간선 리스트에서 가중치가 작은 간선부터 차례대로:
    a. 그 간선이 연결하는 두 정점이 다른 집합에 속해 있다면, 그 간선을 선택하고 두 집합을 합친다.
4. 선택된 간선들로 이루어진 트리가 최소 신장 트리이다.

---

접근 방식 

 

1) MST

MST(최대 신장 트리)의 형태를 띄도록 간선들을 우선적으로 선택하여 두 정점이 연결되는 경로를 찾는 방식으로 해결할 수 있다.

즉, 시작점에서 목표 섬까지 갈 수 있는 여러 경로들 중에서 한 경로 안의 가중치의 최솟값이 가장 큰 경로를 찾는 것이 목적이다.

 

MST를 어떻게 활용할까 ?

해당 경로 안에서의 가중치의 최솟값이 가장 커야한다. 
가중치가 최대가 되는 간선들을 우선 선택하여 두 정점을 연결하고, 그 경로에서의 최솟값을 찾아보자.
즉, 최대 신장트리를 구성한 후 해당 경로 안에서의 최솟값을 찾아보자.

 

2) BFS + Biinary Search

BFS

BFS는 시작 정점에서부터 인접한 정점들부터 차례대로 탐색해 나가는 방식으로,특정 정점에서부터 모든 정점까지의 최단 경로를 찾는 데 주로 사용된다.

즉, BFS는 최단 경로를 찾는데 사용되는 알고리즘이다. 

 

최단경로 찾는 알고리즘 (BFS - 가중치 없음 VS 다엑스트라 - 가중치 있음)

• BFS (Breadth-First Search)
  • 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용된다. 모든 간선의 가중치가 동일(예: 1)하다고 가정할 때, BFS는 출발지에서 목표 정점까지의 최단 경로를 보장한다.
  • BFS는 레벨별로 그래프를 탐색하며, 먼저 방문한 정점이 항상 최단 거리로 도달하게 되므로, 간선의 가중치가 동일한 그래프에서 최단 경로를 정확하게 찾을 수 있다.
• Dijkstra's Algorithm
  • 가중치가 있는 그래프에서 최단 경로를 찾는 데 사용된다. 각 간선에 서로 다른 가중치가 있을 수 있으며, 다익스트라는 출발지에서 목표 정점까지의 최단 경로를 계산할 수 있다.
  • Dijkstra는 우선순위 큐(힙)를 사용하여, 현재까지 발견된 가장 짧은 경로를 가진 정점부터 탐색을 진행한다. 이 방식은 가중치가 있는 그래프에서도 최단 경로를 정확하게 계산할 수 있다.

BFS만 적용하면 안되는 이유

시작점 -> 끝점까지 갈 수 있는 최단 경로(가중치 고려 X)를 구하는 것이 목표가 아니라, 가중치를 고려하여 최대 중량을 견딜 수 있는 경로를 찾는 것이 목표이다.

BFS는 기본적으로 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용된다.
위의 문제에서 각 다리(간선)에는 각각 다른 중량 제한(가중치)가 존재한다. 

따라서, 일반 BFS처럼 queue + visited 배열을 사용하여 방문처리를 하면 안된다. ---> 이렇게 구현 시 가중치를 고려하지 않고, 시작점과 끝점 사이의 최단 경로를 찾을 것이기 때문이다.

 

그렇다면 visited 배열을 쓰지 않으면 될 것 아닌가 ?

안된다. 이미 방문했던 정점들도 queue에 계속 추가될 것이기 때문에 시간초과를 유발할 것이다.

 

Binary Search 도입 

C(1 ≤ C ≤ 1,000,000,000) 사이의 중량의 최댓값을 mid로 설정하자.

이진탐색을 이용하여 최적의 mid값을 찾아 출력하자.

해당 mid값이 최적의 mid값인지 확인하기 위해선 binary_search() 안에서 매번 bfs를 돌려 조건

• 시작점 -> 끝점까지 경로 안에서의 가중치들이 모두 해당 mid 값 이상인지 확인하고 
• 만약 그렇다면, 이상 없이 끝점까지 방문 완료했을 것이다. (visited[end] == True)

을 만족하는지 확인해야 한다.

---

입출력 예시

9 9
1 4 11
1 5 2
4 5 4
4 3 10
4 2 7
5 2 10
5 6 13
3 2 9
2 6 8
1 6
정답 : 9

---

💡 풀이코드 (성공 - MST Prim)

# MST - Prim
import sys 
import heapq 

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    v1, v2, w = map(int, sys.stdin.readline().split())
    graph[v1].append((v2, w))
    graph[v2].append((v1, w))
start, end = map(int, sys.stdin.readline().split())

def prim(N, graph, start, end):
    visited = [False] * (N + 1)
    queue = []
    heapq.heappush(queue, (-sys.maxsize, start))

    while queue:
        w, v = heapq.heappop(queue)

        if visited[v] == False:
            visited[v] = True

            for u, weight in graph[v]:
                if not visited[u]:
                    heapq.heappush(queue, (max(w, -weight), u))
            
            if v == end:
                print(-w)
                return
    
prim(N, graph, start, end)

 

 

최대힙 구성

1)

• graph의 무게값은 양수이므로 음수를 만들어 비교한다.
• 현재 w값(음수)과 인접한 노드의 값(음수) 중 max값을 힙에 넣는다
  즉, 절댓값이 작은 값을 힙에 넣는다.(음수)

def prim(N, graph, start, end):
    heapq.heappush(queue, (-sys.maxsize, start))

    while queue:
		...
        heapq.heappush(queue, (max(w, -weight), u))

 

2)

• 힙의 무게값은 음수이므로 양수를 만들어 비교한다.
• 현재 w값(양수)과 인접한 노드의 값(양수) 중 min값을 찾는다. min값에 -를 붙혀 음수를 만들어 힙에 넣는다.
  즉, 절댓값이 작은 값을 힙에 넣는다.(음수)

def prim(N, graph, start, end):
    heapq.heappush(queue, (-sys.maxsize, start))

    while queue:
		...
        heapq.heappush(queue, (-min(-w, weight), u))

 

즉, 1),2) 중 어떤 방식이든 상관없다.

둘 다 아래와 같은 방식이다.

1.  힙에 min(현재노드의 가중치, 인접한 노드의 가중치)를 삽입한다.
2.  이 때, min값을 음수로 만들어 최대힙을 구성한다. (최대힙을 만들어 가중치가 높은 노드가 먼저 나올 수 있도록 한다.)

 

정리

해당 경로 안의 무게의 최솟값을 찾기 위해 min(현재 노드의 가중치, 인접한 노드의 가중치)을 힙에 넣는다.

 

주요 로직

while문 종료 조건

둘 중 어떤 조건을 사용해도 상관 없다.

둘 다 Prim 알고리즘의 종료 조건에 부합한다.

"우선순위 큐가 비지 않았고, 트리에 포함된 간선이 n-1개가 되지 않았다면"

while cnt <= M: # Prim 알고리즘 종료 조건

while queue:

 

방문 처리

• 해당 정점을 방문하지 않았다면 방문처리를 진행한다.
• 그 후, 해당 정점과 인접한 노드들을 확인한다. 

1) 인접한 노드 방문 여부 확인

• 아래 두 코드 모두 맞는 예시이다.

while cnt <= M:
    w, v = heapq.heappop(queue)
    cnt += 1

    if visited[v] == False:
        visited[v] = True

        for u, weight in graph[v]:
            if not visited[u]:
                heapq.heappush(queue, (-min(-w, weight), u))

while queue:
    w, v = heapq.heappop(queue)

    if visited[v] == False:
        visited[v] = True

        for u, weight in graph[v]:
            if not visited[u]:
                heapq.heappush(queue, (max(w, -weight), u))

 

2) 인접한 노드 방문 여부 확인 X

• 아래 한 코드만 맞는 예시이다.
• while문 종료조건을 while cnt <= M으로 변경하면 틀린다.

while queue:
    w, v = heapq.heappop(queue)

    if visited[v] == False:
        visited[v] = True

        for u, weight in graph[v]:
            heapq.heappush(queue, (-min(-w, weight), u))

 

인접한 노드의 방문 처리의 역할

기존 코드에서 cnt <= M: 조건을 사용할 때, 문제는 큐에 남아 있는 노드를 모두 처리하기 전에 탐색이 중단될 수 있다는 점이었다.

하지만, 1)처럼 인접한 노드를 큐에 추가하기 전에 방문 여부를 확인하는 조건을 추가하면, 큐에 불필요한 노드가 추가되는 것을 방지할 수 있었다.

2)에서는  인접한 노드의 방문 여부를 확인하지 않아 큐에 불필요한 노드가 추가되어 cnt <= M 안에 end까지의 중량의 최솟값에 도달하지 못해 틀리는 경우가 발생한 것이다.

 

정리

방문 여부 확인 후 cnt <= M 사용: 방문 여부 확인을 통해 불필요한 노드를 큐에 추가하지 않도록 제어할 수 있으므로, cnt <= M 조건을 사용하더라도 올바르게 동작할 수 있었다.
탐색 종료 시점: cnt <= M 조건은 일반적으로 큐의 전체 탐색을 보장하지 않지만, 방문 처리가 제대로 이루어지면 필요 없는 추가 탐색을 피하면서도 목표에 도달할 수 있다.
따라서, 방문 여부 확인을 통해 불필요한 탐색을 피하고, cnt <= M 조건을 사용하여 성능을 최적화할 수 있게 된 것이다. 이 방식은 올바르게 동작할 수 있으며, 원래 문제의 요구 사항을 충족한다.

 

정답 출력 

만약 해당 노드가 끝점이라면 힙에서 꺼낸 중량을 음수로 만들어 출력한다.

queue에 pop하지 않은 끝점 노드가 더 남아있을 수 있으므로 출력 후 return한다.

if v == end:
    print(-w)
    return

---

💡 풀이코드 (성공 - MST Kruskal)

# MST - Kruskal
import sys 
import heapq 

N, M = map(int, sys.stdin.readline().split())
graph = []
parent = [0] * (N + 1)

for _ in range(M):
    v1, v2, w = map(int, sys.stdin.readline().split())
    graph.append((-w, v1, v2))
start, end = map(int, sys.stdin.readline().split())
graph.sort() # 가중치가 큰 순서로 정렬 

def init(N):
    for i in range(1, N + 1):
        parent[i] = i 

def find(i):
    while parent[i] != i:
        parent[i] = parent[parent[i]]
        i = parent[i]
    return i

def in_same_set(p, q):
    return find(p) == find(q)

def union(p, q):
    i = find(p)
    j = find(q)

    if i != j:
        parent[i] = j # 오른쪽이 부모

def kruskal(N, M, graph, start, end):
    global parnet 
    init(N)

    for w, v1, v2 in graph:
        p = find(v1)
        q = find(v2)

        if in_same_set(p, q) == False:
            union(p, q)
            
            if in_same_set(start, end):
                print(-w)
                return

kruskal(N, M, graph, start, end)

 

위의 코드는 Kruskal 알고리즘을 거의 100% 활용한 예시이다.

 

주요 로직

• 만약 두 정점이 같은 집합에 있지 않다면, 부모를 같게 만들어준다.
• union()을 수행한 후, 만약 시작점과 끝점이 같은 집합에 있게 되었다면 중량을 출력하고 리턴한다.

if in_same_set(p, q) == False:
    union(p, q)

    if in_same_set(start, end):
        print(-w)
        return

---

💡 풀이코드 (성공 - BFS + Binary Search)

# BFS + Binary Search
import sys 
from collections import deque 

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    v1, v2, w = map(int, sys.stdin.readline().split())
    graph[v1].append((v2, w))
    graph[v2].append((v1, w))
start, end = map(int, sys.stdin.readline().split())
        

def bfs(m):
    global graph, start, end
    visited = [False] * (N + 1)
    visited[start] = True 
    queue = deque()
    queue.append((start,0))

    # for v, w in graph[start]: # 문제 start와 바로 연관된 11과 2는 검사 안하는 문제
    #     queue.append((v, w))

    while queue :
        v, w = queue.popleft()

        for nv, nw in graph[v]:
            if visited[nv] == False:
                if nw >= m: 
                    queue.append((nv, nw))
                    visited[nv] = True 

    if visited[end] == True: return True 
    else: return False

def binary_search(left, right):
    answer = 0
    while left <= right:
        mid = (left + right) // 2 # 최대 중량 

        if bfs(mid): 
            left = mid + 1 
            answer = mid
        else: 
            right = mid - 1
    print(answer)

                
binary_search(1, 1000000000)

 

초기 틀린 이유

초기에 틀렸던 이유가 queue의 초깃값 설정을 잘못해서였다.

아래처럼 시작점과 인접한 노드를 미리 queue에 삽입한다면 시작점과 인접한 노드들은 while문 안의 로직을 수행하지 않게 된다.

즉, 시작점과 인접한 노드들은 bfs()의 인자로 받은 mid값과의 비교를 진행하지 않은채 모든 로직을 수행하게 되므로 문제가 발생한다.

for v, w in graph[start]: # 문제 start와 바로 연관된 11과 2는 검사 안하는 문제
    queue.append((v, w))

 

BFS

• 만약, 인접한 노드를 아직 방문하지 않았고, 인접한 노드의 중량이 mid 이상이라면 큐에 삽입한다.
  이는, 시작점 -> 끝점까지 경로 안에서의 가중치들이 모두 해당 mid 값 이상인지 확인하는 과정이다.
• 만약 그렇다면, 이상 없이 목적지인 끝점까지 방문을 완료했을 것이다. (visited[end] == True)

while queue :
    v, w = queue.popleft()

    for nv, nw in graph[v]:
        if visited[nv] == False:
            if nw >= m: 
                queue.append((nv, nw))
                visited[nv] = True 

if visited[end] == True: return True 
else: return False

 

이진 탐색

• 만약 bfs()에서 끝점까지 방문이 가능했다면 해당 mid보다 더 큰 중량의 최댓값이 가능할지도 모른다. 
  따라서 left를 mid + 1로 설정한다.
• 그렇지 않다면 해당 mid값으로 설정했을 시 끝점까지 방문을 못했다는 의미이므로 right를 mid - 1로 설정한다.

def binary_search(left, right):
    answer = 0
    while left <= right:
        mid = (left + right) // 2 # 최대 중량 

        if bfs(mid): 
            left = mid + 1 
            answer = mid
        else: 
            right = mid - 1
    print(answer)

---

💡 풀이코드 (실패 - BFS )

import sys 
from collections import deque 

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    v1, v2, w = map(int, sys.stdin.readline().split())
    graph[v1].append((v2, w))
    graph[v2].append((v1, w))
start, end = map(int, sys.stdin.readline().split())

def bfs(N, M, graph, start, end):
    visited[start] = True 
    queue = deque()
    queue.append((1,sys.maxsize))

    # for v, w in graph[start]:
    #     queue.append((v, w))
    ans = 0

    while queue :
        v, w = queue.popleft()
        visited[v] = True

        if v == end: 
            ans = max(ans, w)

        for nv, nw in graph[v]:
            if visited[nv] == False:
                queue.append((nv, min(w, nw)))
                # visited[nv] = True

    print(ans)
                
bfs(N, M, graph, start, end)

 

BFS는 가중치가 없는 그래프의 최단경로를 찾는 알고리즘이므로, BFS만을 사용하면 당연히 틀린다.

---

참고문헌

https://gliver.tistory.com/40

[18강] 최소 신장 트리 (MST)

 

https://hbj0209.tistory.com/132

[Python] BOJ 1939 - 중량제한

https://jie0025.tistory.com/212

[BOJ - 이분탐색] 1939번 : 중량제한 (python)