백준 1939 파이썬 문제풀이

문제

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일 때는 될 수 있지만, 4일 때는 답이 될 수 없다는 것을 알 수 있다. 즉, 특정한 최대/최소값을 찾는 문제이기 때문에 이진 탐색을 통해 값을 계속 찾아낼 수 있다. 시간복잡도는 log2(n)이 소모된다.

그래프를 탐색하는 것은 BFS로 접근을 했다. 특정한 값을 만족할 경우에만 계속 탐색이 가능하도록 설정했다. BFS로 접근할 때는 방문 체크 배열을 작성해두었는데, 이는 방문했던 지점을 동일한 이력으로 계속 방문하는 것을 막아 메모리 초과 및 시간 초과를 해결하기 위해 작성했다. 

그렇다면 방문 리스트를 설정해서 큐에 넣는 값을 제한하는 것이 논리적으로 문제가 없는지를 살펴보는 것도 중요하다. 다음과 같은 경우를 생각해보자

1. A → B일 때, A에서 B로 바로 올 수 있는 경우
   A → B 경로가 어떻든 아무 상관이 없다. 왜냐하면, 이미 B로 오는 방법에 대해 확인이 끝나고, 그 결과 B에서 그 다음 노드로 이동을 했다. 따라서, A → C → B 경로로 와서, B에서 다시 뻗어나가는 경우는 더 이상 고려할 필요가 없어진다.
2. A → B일 때, 중량 때문에 다른 경로를 타고 와야하는 경우
   중량으로 인해 직접적으로 오지 못해, 다른 다리를 거쳐서 온다. 따라서 이 때, B의 방문 배열은 0으로 관리되고 있고, A → C → B 한 후에 처음으로 방문한다. 그리고 지금부터 B에 대해서 탐색을 해나가기 때문에 온당하다.
3. 왔던 길을 돌아가야하는 경우 
   이런 경우는 문제 상황을 고려해봤을 때, 온당치 않다.

따라서 방문 배열을 관리해서 답을 구하는 방식에서 논리적 문제는 없음을 유추할 수 있다. 위의 내용을 종합해보면 아래와 같이 코드를 작성할 수 있다.

import sys
from collections import deque


def bfs(my_list, value, start, end, n) :
    
    ### 변수 선언
    que = deque()
    v = [0 for _ in range(n+1)]
    
    # 방문 처리 및 시작지점 que에 넣음.
    v[start] = 1
    que.append(start)
    
    
    while que :
        asis = que.popleft()
        # 현재 위치가 end라면 종료
        if asis == end :
            return True

        # 무게 하중이 현재 다리의 limit보다 낮을 경우 추가 탐색함.
        for togo, limit in my_list[asis]:
            if limit >= value and v[togo] == 0:
                que.append(togo)
                v[togo] = 1
    return False


# 변수 입력 받기
n,m = map(int,sys.stdin.readline().split())
my_list = [[] for _ in range(n+1)]
for _ in range(m) :
    a,b,c = map(int,sys.stdin.readline().split())
    my_list[a].append((b,c))
    my_list[b].append((a,c))
s,e = map(int,sys.stdin.readline().split())
l,r = 0, sys.maxsize
answer = 0


# 이진 탐색. 
# 현재 값을 만족하는 부분은 계속 고려가 필요함. l = mid
# 현재 값을 만족하지 않는 부분을 계속 고려하지 않아도 됨. r = mid - 1 
while l < r :
    mid = (l + r +1 ) // 2
    if bfs(my_list, mid, s, e, n) :
        l = mid
        answer = mid
    else :
        r = mid - 1

print(answer)