13905. 세부 (Python)

 

13905번: 세부

 

풀이

 모든 경로를 탐색해가면서 최대 개수를 구하면 시간초과가 발생한다. 따라서 처음부터 모든 경로를 탐색하는 것이 아니라 임의의 개수 k개를 혜빈이의 위치까지 들고갈 수 있는 경로가 있는지를 탐색하면 된다. 임의의 개수 k개는 이분 탐색을 사용하여 정할 수 있다. 즉, 이분 탐색과 BFS를 사용하여 문제를 해결하면 된다.

 

코드

import sys
from collections import deque
input = sys.stdin.readline


# base개를 사용하여 s에서 e로 갈 수 있는지를 BFS를 사용하여 체크
def bfs(base):
    q = deque()
    q.append(s)  # s부터 시작
    visited = [False for _ in range(N+1)]
    visited[s] = True

    while q:
        now = q.popleft()

        if now == e:  # e에 도달했다면 True를 반환
            return True

        for nextHouse, nextCount in graph[now]:
            # base개를 들고갈 수 없는 경로라면 continue
            if visited[nextHouse] or nextCount < base:
                continue

            q.append(nextHouse)
            visited[nextHouse] = True

    return False  # e에 도달하지 못했다면 False 반환


if __name__ == '__main__':
    N, M = map(int, input().split())
    s, e = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    visited = [-1 for _ in range(N+1)]

    left, right = 1, 1
    for _ in range(M):
        h1, h2, k = map(int, input().split())
        graph[h1].append((h2, k))
        graph[h2].append((h1, k))
        right = max(right, k)

    res = 0
    # 이분 탐색을 사용하여 들고갈 수 있는 빼빼로의 최대 개수를 구한다.
    while left <= right:
        mid = (left + right) // 2

        if bfs(mid):  # mid개를 s에서 e까지 들고갈 수 있는 경로가 있는 경우
            res = mid
            left = mid + 1
        else:
            right = mid - 1

    print(res)