[백준1939&파이썬] 이진탐색 BFS에 응용하기, 이진탐색 경계값 설정에 주의하자.

# 문제

백준1939 중량제한 파이썬 풀이

1939번: 중량제한

# 코드

'''
  - 노드간 여러개 엣지가 존재 할 수 있다.
  - 양방향 다리이다.
  - DFS + 백트래킹을 활용해서 길의 최대값을 구한다 -> 시간초과 or 메모리 초과
  - 모든 경우의 수를 구하고 거기서 최대값을 구한다 -> 시간초과 or 메모리 초과
  - 이분탐색 시간복잡도 -> O(logN)
    - 0 ~ 10억의 경우의 수에서 해당 값을 경로가 넘어버리는지 아닌지를 확인한다
    - O(log 10억) 은
    - 도착점까지의 길은 무조건 있다.
'''
import sys
from collections import defaultdict
from collections import deque

MAX = 1_000_000_000  # 10억
N, M = map(int, sys.stdin.readline().split())  # N : 노드, M : 엣지
graph = defaultdict(list)
# graph = [[] for _ in range(N + 1)]

for _ in range(M):
  a, b, c = map(int, sys.stdin.readline().split())
  # 양방향 다리
  graph[a].append((b, c))
  graph[b].append((a, c))


start, end = map(int, sys.stdin.readline().split())
left = 1
right = MAX
result = -1
while left <= right:
  mid = (left + right) // 2  # 이 값이 중량 값임, 이값으로 도착이 가능한지 판단하면 됨

  # 도착점까지의 길이 무조건 있기 때문에, mid값보다 크거나 같은 간선만 선택해서 가자
  dq = deque()
  dq.append(start)
  visit = [False] * (N + 1)
  visit[start] = True
  isFinish = False

  while len(dq) != 0:
    cur = dq.popleft()
    for neighbor in graph[cur]:  # neighbor : (vertex, cost)
      if mid <= neighbor[1]:
        if visit[neighbor[0]] == False:  # 방문했던 곳이 아니라면
          visit[neighbor[0]] = True
          dq.append(neighbor[0])

          if neighbor[0] == end:  # 도착했으면, 범위를 키워봄
            left = mid + 1
            isFinish = True
            dq.clear()
            result = mid
            break
  if not isFinish :
    right = mid - 1  # 도착을 못했기 때문에 범위를 줄임

print(result)

# 풀이

• DFS(백트래킹)을 사용해서 끝까지 계속 도달시키는 값을 확인하고, 끝점에 도착했을때 값보다 더 크게 움직여야지만 가능하도록 하는 코드를 작성했으나 시간초과가 발생했다.
• 이분탐색을 이용해서 문제를 해결 할 수 있다. 간선의 갯수가 최대 10억개까지이기 때문에 완전탐색으로 모든 경우를 구하는 것은 당연히 불가능하다.
• 그렇다면 이분탐색으로 선택된 MID의 대해서 현재 BFS로 탐색했을 시, MID값 이상을 넘기는지 못넘기는지 YES / NO 의 여부로 판단하여 최적의 값을 찾아내면 된다. start=1 , end = 10억으로 하여 찾는 최적의 cost를 이분탐색을 진행한다. 이분탐색의 시간복잡도는 O( log C ) 이다.(C는 10억) 그렇기 때문에 29번의 탐색만 거치면 값을 찾아낼 수 있다. 
• 결국 29 * O( V + E )  = O( 29 ) * O ( 10,000 + 100,000 ) 이기 때문에 적정 시간안에 탐색을 끝낼 수 있다.

## 삽질

• 이분탐색 경계설정을 잘못하고 있어서 시간초과가 났고, 1시간동안 헤맸다.
• binary(left,right) 일때, 경계값 넘겨주는걸 left = mid -1 , right = mid로 해줬다. 왜냐하면 성공했을 경우 mid일 수도 있다는 생각이었다. 그러고 while문 탈출 조건을 left != mid로 해줬었는데 여기서 계속 무한루프에 빠졌다. 
  • 왼쪽으로 재탐색 해야하는 경우 right = mid -1 
  • 오른쪽으로 재탐색 해야하는 경우 left = mid 
  • 탈출 조건 left != right
• 위의 케이스처럼이 아닌 아래와 같이 수정했더니 정답이 됐다.
  • 왼쪽으로 재탐색 해야하는 경우 right = mid -1
  • 오른쪽으로 재탐색 해야하는 경우 left = mid +1
  • 탈출 조건 left <= right 

 

• 이진탐색의 경계 조건이 생각보다 헷갈리는거 같다. 시간날때 공부해야겠다. 

Binary Search Lower Bound와 Upper Bound

# 참고

공장끼리 연결하는 섬의 경로가 항상 존재하기 때문에 크루스칼을 사용하여 MST(이런 경우에는 MAX SPANNING TREE )을 찾아도 해결이 가능하다.