Algorithm TIL (241001)

1️⃣ [백준] 중량제한

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

 

🔥다시 풀어보기 🔥

 

문제 풀이 과정

• x섬에서 y섬으로 이동할 때, 이동 가능한 최대 중량을 구하는 문제
• 문제를 읽고 마땅한 자료구조가 생각나지 않았다.
• 처음 아이디어 : BFS로 탐색하면서 가능한 중량의 최댓값을 구한다. (실패:적절하지 못한 분기처리, 시간초과)
• 참조 아이디어 : 우선순위 큐 최대힙 이용

문제 풀이

• 동작 과정
  1. 시작노드를 우선순위큐에 넣고 초기화한다.
  2. 인접노드를 확인한다
     • 현재 노드 중량과 인접노드 중량 중 작은 값(새로운 중량)을 구한다.
     • 인접노드 중량이 새로운 중량보다 작다면 견딜수 있으므로 인접노드 중량을 새로운 중량으로 변경한다.
     • 변경한 인접노드와 새로운 중량을 큐에 넣는다.
  3. 2번을 반복한다.
• python

'''
중량제한

x에서 y로 이동하는 경로 중 최대 중량
x-y이동시 가능한 중량값을 계산해서 그 중 최대값을 출력한다.
x-y이동시 가능한 중량값은, 매번 최대 중량을 선택한다.
'''
import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split()) # 섬의 개수, 다리의 정보 개수
graph = [[] for _ in range(N+1)]
for _ in range(M) :
    A, B, C = map(int, input().split()) # a섬과b섬 사이 c중량제한 다리
    graph[A].append((B,C))
    graph[B].append((A,C))
    
start, end = map(int, input().split()) #공장이 위치한 섬 번호
visited = [False] * (N+1) # 방문확인 리스트
dist = [-1] * (N+1) # 최소중량 테이블

def func(start) :
    # 시작 노드 초기화
    dist[start] = int(1e9)
    q = []
    
    # 우선순위 큐에 (중량, 노드)형태로 넣어준다. (최대 중량을 우선순위 큐로 구현하기)
    heapq.heappush(q, (-int(1e9), start))
    
    while q :
        # 최대 증량 뽑기
        cur_weight, cur_node = heapq.heappop(q)
        cur_weight = -cur_weight 
        # 이미 처리된 노드는 스킵
        if dist[cur_node] > cur_weight :
            continue
        # 인접한 노드들을 확인하며 중량 비교
        for next_node, next_weight in graph[cur_node] :
            new_weight = min(cur_weight, next_weight) # 현재 경로에서의 최소 중량을 구한다.
            # 새로운 경로가 더 큰 중량을 견딜 수 있으면 업데이트
            if dist[next_node] < new_weight :
                dist[next_node] = new_weight
                heapq.heappush(q, (-new_weight, next_node))

func(start)
print(dist[end])

 

다른 방법

• BFS - 이분탐색
• 동작 과정은 아래와 같다.
  1. 경로의 최소값과 최댓값을 설정한다. (1 <= C <= 1000000000)
  2. 경로의 중간값을 찾는다.
  3. 중간값을 BFS 탐색을 통해 해당 중량이 이동할 수 있는지 확인한다.
     1. 이동할 수 있다면 중간값을 결과값으로 세팅한다. 그리고 최대 중량이므로 경로의 최소값을 중간값 + 1 로 이동
     2. 이동할 수 없다면 최대값을 중간값 - 1 로 이동
  4. 중간값에 대해 BFS 탐색을 못할 때까지 3번을 반복한다.

 

느낀 점 회고

• 이 문제를 보고 어떻게 풀어야 하는지 감이 오지 않았다. 다익스트라, 플로이드 워셜, 이분탐색 등 그래프 탐색에서 좀 더 많은 문제를 풀어볼 필요가 있다.
• 구현은 했으나 완벽히 체화하려면 나중에 다시 한번 풀어 보자