K번째 수

출처 : 백준 #1939

시간 제한	메모리 제한
1초	128 MB

---

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

---

출력

첫째 줄에 답을 출력한다.

---

입출력 예시

예제 입력 1

3 3
1 2 2
3 1 3
2 3 2
1 3

예제 출력 1

3

---

풀이

생각

• 처음에는 링크드 리스트로 풀었다가 시간초과가 나왔다.
• 이유는 링크드 리스트를 탐색하는 bfs 함수에서 받는 과정이 시간이 오래걸린 모양인 듯 보였다.(확실하지 않아 확인을 다시 해 볼 필요가 있음)
• 따라서 list of lists 방식으로 인접리스트를 구성하여 풀게되었다.

풀이 설명

• w를 입력받을 때 최대값을 가지는 w를 max_weight로 기록해둔다.
• 그래서 1과 max_weight의 중간인 mid를 설정하고 해당 무게 이상인 것만 건너서 목적지에 도착할 수 있는지를 확인한다.
• 목적지에 도착할 수 있다면, 당시의 mid 값을 answer에 기록해 둔다.
  • 그리고 left 값을 mid + 1로 업데이트하여 추가적으로 탐색한다.
• 만약 목적지에 도착할 수 없다면, 중량을 더 낮춰야 하므로, right 값을 mid - 1로 업데이트 하여 추가적으로 탐색한다.

python code

# 백준 1939번
from sys import stdin
import sys
from collections import deque
sys.setrecursionlimit(10**6)

class Node:
    def __init__(self, vertex, weight):
        self.vertex = vertex
        self.weight = weight
        self.next = None

class Graph:
    def __init__(self, size):
        self.adjList = [None] * (size+1) # 0은 없으므로
        self.adjList2 = [[] for _ in range(size+1)]
        self.size = size+1

    def insertEdge(self, v1, v2, w):    # linked list
        newNode = Node(v2, w)
        newNode.next = self.adjList[v1]
        self.adjList[v1] = newNode

        newNode = Node(v1, w)
        newNode.next = self.adjList[v2]
        self.adjList[v2] = newNode

    def bfs(self, start, dest, box_weight):
        visited = [False] * (self.size+1)
        queue = deque([start])
        visited[start] = True

        while queue:
            w = queue.popleft()
            if w == dest:
                return True
            node = self.adjList[w]
            while node is not None:
                if visited[node.vertex] == False and node.weight >= box_weight:
                    visited[node.vertex] == True
                    queue.append(node.vertex)
                node = node.next
        return False

    def insertEdge2(self, v1, v2, w):   # list of lists
        self.adjList2[v1].append((v2, w))
        self.adjList2[v2].append((v1, w))

    def bfs2(self, start, dest, box_weight):
        visited = [False] * (self.size+1)
        queue = deque([start])
        visited[start] = True
        while queue:
            w = queue.popleft()
            if w == dest:
                return True
            for vertex, weight in self.adjList2[w]:
                if visited[vertex] == False and weight >= box_weight:
                    visited[vertex] = True
                    queue.append(vertex)
        return False


    def findFactory(self, start, dest, max_weight):
        left = 1
        right = max_weight
        answer = 0
        while left <= right:
            mid = (left+right)//2
            if self.bfs2(start, dest, mid) == True:
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return answer


n, m = map(int, stdin.readline().split())
g = Graph(n)
max_weight = 0
for _ in range(m):
    v1, v2, w = map(int, stdin.readline().split())
    if max_weight < w:      # 중량 최댓값 구하기
        max_weight = w
    g.insertEdge2(v1, v2, w)

f1, f2 = map(int, stdin.readline().split())
result = g.findFactory(f1, f2, max_weight)
print(result)