• 출처 : https://www.acmicpc.net/problem/1939

• 알고리즘 : 이진 탐색, 너비 우선 순회

• 풀이

  1. set 에지 연결 리스트
  2. BFS in 이진 탐색

• 이진 탐색 구현

  1. mid = (low + high) // 2
  2. mid 이상인 cost로 출발지부터 도착지까지 갈 수 있을 경우(BFS)
     1. low = mid + 1
  3. 갈 수 없을 경우
     1. high = mid - 1

• BFS 구현

  1. 전형적인 BFS에서
  2. 최소 cost (mid) ≤ 현재 에지 cost 일 경우 이동

• 소감

  • 처음에 DFS로 모든 경로를 찾아 cost의 최솟값의 최댓값을 찾으려 했다
  • 시간 초과가 났다
  • 풀이를 참고했으나 BFS구현에서 자꾸 틀렸다
  • 이진 탐색으로 최소 cost를 찾아나가야 하는데 최대 cost를 찾고 있었다

틀린 코드

# 시간 초과
import sys
sys.setrecursionlimit(99999)

def dfs(start, min_cost):
    visited[start] = True
    if start == end:
        min_list.append(min_cost)
    for key in b_dict[start]:
        if not visited[key]:
            dfs(key, min(min_cost, b_dict[start][key]))
    visited[start] = False


def init():
    i_num, b_num = map(int, sys.stdin.readline().rstrip().split(' '))
    b_list = []
    for i in range(b_num):
        a,b,c = map(int, sys.stdin.readline().rstrip().split(' '))
        b_list.append((a,b,c))
    start, end = map(int, sys.stdin.readline().rstrip().split(' '))
    return i_num, b_num, b_list, start, end


def to_dict():
    b_dict = dict()
    for bridge in b_list:
        a,b,c = bridge
        if a not in b_dict:
            b_dict[a] = dict()
        if b not in b_dict[a]:
            b_dict[a][b] = c
        else:
            b_dict[a][b] = max(b_dict[a][b], c)
        if b not in b_dict:
            b_dict[b] = dict()
        if a not in b_dict[b]:
            b_dict[b][a] = c
        else:
            b_dict[b][a] = max(b_dict[b][a], c)
    return b_dict


i_num, b_num, b_list, start, end = init()
b_dict = to_dict()
visited = [False] * (i_num + 1)
min_list = []
dfs(start, float('inf'))
print(max(min_list))

맞은 코드

import sys
from collections import deque

def bfs(min_cost):
    q = deque()
    q.append(start_vertex)
    visited = [False] * (vertex_num + 1)
    visited[start_vertex] = True
    while len(q) > 0:
        curr = q.pop()
        # 도착했을 경우
        if curr == end_vertex:
            return True
        for vertex, cost in edge_list[curr]:
            if not visited[vertex]:
                # min_cost 이상일 경우
                if min_cost <= cost:
                    # 이동
                    visited[vertex] = True
                    q.append(vertex)
    return False


def binary_search(low, high):
    # low가 high를 초과했을 경우 값이 작은 high 리턴
    if high < low:
        return high
    mid = (low + high) // 2
    # min_cost == mid 일 때 도착 가능할 경우
    if bfs(mid):
        return binary_search(mid + 1, high)
    # min_cost == mid 일 때 도착 불가능할 경우
    else:
        return binary_search(low, mid - 1)


# init
vertex_num, edge_num = map(int, sys.stdin.readline().rstrip().split(' '))
edge_list = [[] for i in range(vertex_num + 1)]
for i in range(edge_num):
    a,b,c = map(int, sys.stdin.readline().rstrip().split(' '))
    edge_list[a].append([b,c])
    edge_list[b].append([a,c])
start_vertex, end_vertex = map(int, sys.stdin.readline().rstrip().split(' '))

print(binary_search(0, 1000000000))