백준 1939번: 중량제한 (G3) - Python 풀이

종.스 2주차의 마지막 과제.
미루고 미루던 바로 골드 3 문제입니다.
....

누군지는 안 알려드리겠습니다.
심신의 안정이 필요할 것 같아서 잠시 쳐다보는 시간을 갖겠습니다.
3
2
1

Let's go

문제 설명

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

빠른 이해를 돕기 위해 방금 그려온 그림입니다.

솔직히 블로그 쓰는 거 너무 오래 걸려서 이것만 첨부하고 넘어가고 싶지만 미래의 제가 다시 보았을 때 이해 못 할 것 같습니다.
기록은... 다 미래를 위하는 일입니다.

섬의 개수 N, 그 섬들을 잇는 다리의 개수 M이 있습니다.
다리에 대한 정보로 A B C 가 주어지고, 이는 'A에서 B로 가는 다리는 C만큼의 중량제한이 있다'는 뜻입니다. 다리는 양방향이고, 두 섬을 잇는 다리가 여러 개일 수 있습니다.
중량이 C를 초과하는 물품이 이 다리를 지나게 되면 다리는 무너지게(...) 됩니다.
입력의 마지막 줄에 시작 섬과 도착 섬이 주어지고, 시작 섬에서 도착 섬까지 이동할 때 옮길 수 있는 물품의 최대 중량을 구해야 합니다.

• 2 ≤ N ≤ 10,000
• 1 ≤ M ≤ 100,000
• 1 ≤ A, B ≤ N
• 1 ≤ C ≤ 1,000,000,000 (십억)

입출력 예시

3 3
1 2 2
3 1 3
2 3 2
1 3

3

 

풀이 과정

쉽게만 살아가면 재미없습니다.

"백준을 풀고 나니 하루가 사라졌다"
제가 인스타도 잠시 디톡스 좀 하려고 비활 타고 해서 뭐 하고 사냐는 말을 듣는데 제가 하는 말은 늘 똑같습니다.

그냥 코테 풀면서 지냅니다

 
오답 과정을 찬찬히 설명해 보자면,
우선 딱 보니까 시작 섬에서 출발 섬까지의 경로가 필요하지 않습니까?
그래서 당당히 DFS를 사용했습니다.
하다보니 그냥 DFS로 탐색하는 과정 속에서 답을 찾을 수 있을 것 같았습니다. 이분탐색을 어디서? 왜 쓰지? 라고 생각했습니다.
접근을 잘못 했고 그렇게 4번의 메모리 초과를 받게 됩니다.
시작 섬에서 도착 섬까지의 모든 경로를 구하는 게 메모리 초과까지 낼 정도인가? 했습니다.
 
아직도 메모리 초과의 원인은 모르겠습니다만~
모든 경로를 다 저장할 필요가 없습니다.
어떻게 이분탐색을 적용할 수 있을까요.

출처: https://tobeforest.tistory.com/60

제가 바로 이전 글에서 적었던 문장입니다. 이 문제까지 다 풀고나서 쓴 글이라... 저걸 안 채로 풀었으면 잘 풀었을 것 같습니다.
다시 보니 '어느 조건 이상일 때 결과가 참'인 문제의 논리가 여기서도 적용됩니다.

우리는 또 최댓값을 구해야 하니, 위의 입출력 예시를 가져와서 중량이 1,2,3, ... 이렇게 증가한다고 할 때, 1부터 3까지 갈 수 있는지 없는지 확인해 보겠습니다.
우선 현재 물품의 중량이 1이라면, 1에서 3까지 갈 수 있나요? -> 네.
중량이 2라면, 1에서 3까지 갈 수 있나요? -> 네.
중량이 3이라면, 1에서 3까지 갈 수 있나요? -> 네.
중량이 4라면, 1에서 3까지 갈 수 있나요? -> 못 갑니다. 다리가 무너집니다.

이런 구조를 가졌으니 이분탐색 알고리즘을 적용해서 풀면 되겠습니다.

1) 이분탐색의 기준 값 설정하기

문제에서 원하는 값이 '물품의 중량'이기 때문에 이 값을 기준으로 이분탐색을 시도합니다.

2) 이분탐색을 위한 값의 최소, 최대 설정하기

가능한 최소 중량과 최대 중량은 주어진 다리의 정보 A, B, C에서 C의 최솟값과 최댓값으로 설정합니다.

3) 범위 반절씩 줄여가며 이분탐색 Let's go

사실 이 문제도 그냥 아이디어가 제일 중요한 것 같습니다.

'중량을 늘려가며, 해당 중량으로 시작 섬에서 도착 섬까지 갈 수 있는 경로의 유무를 확인한다. 계속 늘리다가 경로가 없어지기 직전이 최대 중량.'

는 아이디어. 저도 여러 번의 오답 이후 검색을 통해 깨달을 수 있었습니다.

from collections import deque

# 섬의 개수와 다리의 개수 입력
island_num, bridge_num = map(int, input().split())
# 섬의 정보를 저장할 그래프 변수
graph = [[] for _ in range(island_num+1)]

# 다리 정보를 입력 받을 때 최소 중량과 최대 중량을 구하기 위한 변수 초기화
min_weight = 1000000000
max_weight = 0

# 다리 정보 입력
for i in range(bridge_num):
    A, B, C = map(int, input().split())
    # A섬에서 B섬으로 갈 때 C만큼의 중량까지 버티기 가능
    graph[A].append((B, C))
    graph[B].append((A, C))
    # C의 최솟값을 찾아서 저장
    if min_weight > C: min_weight = C
    # C의 최댓값을 찾아서 저장
    if max_weight < C: max_weight = C

# 시작 섬과 도착 섬 입력
arrival, destination = map(int, input().split())

# BFS를 통해 start에서 end까지 limit 중량을 버틸 수 있는 경로의 유무를 확인
def BFS(graph, start, end, visited, limit):
    # start 방문 처리
    visited[start] = True
    # 큐에 넣어서 초기화
    queue = deque([start])
	
    # 큐가 비어 있지 않으면 반복
    while queue:
        # 큐의 맨앞 값 pop
        island = queue.popleft()
        # 지금 확인하는 섬이 도착 섬이라면
        if island == end:
            # 경로가 존재하는 것이니까 True 반환
            return True
        # 지금 확인하는 섬의 이웃 섬들을 확인
        for neighbor in graph[island]:
            # 아직 방문하지 않은 섬이고, limit을 버틸 수 있는 다리를 가졌다면
            if not visited[neighbor[0]] and neighbor[1] >= limit:
            	# 방문하고 큐에 추가
                visited[neighbor[0]] = True
                queue.append(neighbor[0])
                
    # 큐가 빌 때까지 도착 섬이 없었다면 경로가 없다는 말이니까 False 반환
    return False

# 유효한 범위일 때 반복
while min_weight <= max_weight:
    # 중간 값 weight 생성
    weight = (min_weight + max_weight) // 2
    # 방문 여부 초기화 <- BFS 돌 때마다 새 상태여야 하니까 이 안에서 초기화
    visited = [False for _ in range(island_num+1)]
    # 시작 섬에서 도착 섬까지 weight를 견디며 갈 수 있는 경로가 존재하나요?
    if BFS(graph, arrival, destination, visited, weight):
    	# 존재하면 중량 범위를 넓힌다
        min_weight = weight + 1
    # 버틸 수 있는 경로가 존재하지 않음 <- 지금 중량이 너무 크다는 말이니까
    else:
    	# 중량 범위를 좁힌다
        max_weight = weight - 1

# 다 돌고 났을 때 max_weight이 옮길 수 있는 최대 중량
print(max_weight)

공유기 설치와 중량제한, 둘 다 정리하고 나니 꽤나 비슷한 문제였네요.
중량제한은 BFS를 통해 가능과 불가능의 여부를 확인하고, 그 결과에 맞게 중량을 늘릴지 줄일지 확인하는 단소증가/단소감소의 관계를 지니는 문제였습니다!
드디어 좀 감을 잡은 것도? 같습니다. (유언)
계속 정진하겠습니다.

이상입니다.
안녕히 주무세요!