백준 1939 중량제한 문제풀이

문제 

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

1939번: 중량제한

 

 

 

문제 접근 방식

모든 다리에 중량에 대한 정보가 존재하며, A <> B 지점을 이동할 수 있는 트럭의 최대 중량을 구하는 최적화 문제이다.

이 문제의 경우 특정 무게의 트럭으로 A 와 B 사이를 건널 수 있는가? 라는 결졍문제(답이 yes or no 로 나오는 문제)로 쉽게 바꿀 수 있고, 이 특정 무게의 범위가 1에서 1e9로 연속하기 때문에 파라메트릭 서치를 사용가능하다.

 

특정 무게의 트럭으로 A 와 B사이를 건널 수 있는지 여부를 확인하는 함수는 bfs 를 사용해서 문제를 풀었고,

특정 무게를 설정하는 부분은 Binary Search(이분탐색)을 활용하였다.

 

 

시간 복잡도

트럭의 최대 가능 중량이 1e9 이고 파라메트릭 서치 시 시간 복잡도는 O(logN)

 

BFS의 시간복잡도는 인접 리스트 기준으로 O(V+E) 이고, V와 E 의 최대값은 각각 1e4, 1e5, 여기서는 O(E) 로 봐도 무방하겠다.(E 가 V보다 10배 크므로 V 생략)

 

즉 시간복잡도는 O(logN) x O(E) = O(ElogN), E<=1e5, N<=1e9.

1초이내임을 알 수 있다.

 

 

코드

import sys

input =sys.stdin.readline
MAX=int(1e9)

def bfs(start,w):
    visited=[0]*(n+1)
    q=[start]
    visited[start]=1

    # 공장의 시작지점에서 부터 인접 노드들을 순회한다.
    while q:
        node=q.pop(0)

        # 설정한 무게로 다른 공장에 도착했다면 True 반환
        if node == fb:
            return True

        # 인접한 섬들을 중 갈 수 있는 섬들을 큐에 넣어준다.
        for next,weight in islands[node]:
            if visited[next]==0 and weight>=w:
                q.append(next)
                visited[next]=1


    return False


if __name__=='__main__':
    global n,e,islands
    n,m=map(int,input().split())

    #인접 리스트
    islands=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        islands[a].append((b,c))
        islands[b].append((a, c))

    fa,fb=map(int,input().split())

    s,e=1,MAX
    mid=(s+e)//2
    answer=0

    #Binary Search를 사용하여 무게를 조절해나감.
    while e>=s:
        if bfs(fa,mid):
            answer=mid
            s=mid+1
        else:
            e=mid-1
        mid=(s+e)//2

    print(answer)

 

 

회고

 

초기 문제를 풀 때, A공장에서 B공장으로 이동이 가능한지 판단하는 함수를 DFS 로 구현을 했는데 Recursion Error 가 나왔음. 뭔가해서 봤더니 백준에서 재귀함수의 최대 횟수인 1000회를 초과해서 발생한 문제였다. DFS로는 에러가 났기에 BFS로 변경하여 문제를 풀 수 있었다.

 

그리고 좀 더 빠른 풀이법은 어떤 방식으로 풀었는지 보니 유니온 파인드 트리를 활용해서 좀 더 빠르게 문제가 해결된 것을 볼 수 있었다. 이번에 풀었던 파라메트릭에 대해 정리한 후, 유니온 파인드로도 풀어야겠다