코딩고치

[파이썬][백준] 1939번: 중량제한 본문

파이썬/백준 문제

[파이썬][백준] 1939번: 중량제한

코딩고치 2020. 6. 5. 00:06

1. 문제

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

 

1939번: 중량제한

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리

www.acmicpc.net

문제 유형: BFS, 이진 탐색

 

  • 중량 제한이 1,000,000,000이므로 일반적인 탐색으로 풀 수 없음
    • log나 $\sqrt{}$를 이용하는 방식으로 풀여야 함 (약 3,000,000개로 연산이 줄어듦)
  • 각 노드와 간선을 입력받은 후 중량의 최댓값과 최솟값을 찾음
  • BFS로 간선을 확인하면서 현재 중량으로 다리를 건널 수 있는지 확인
    • 가능한 경우 최솟값 = 현재 중량 + 1로 설정 후 반복
    • 불가능한 경우 최댓값 = 현재 중량 - 1로 설정 후 반복
저작자표시 비영리 변경금지

'파이썬 > 백준 문제' 카테고리의 다른 글

[파이썬][백준] 1991번: 트리 순회  (0) 2020.06.05
[ 파이썬][백준] 2110번: 공유기 설치  (0) 2020.06.04
[파이썬][백준] 1236번: 성 지키기  (0) 2020.05.31
[파이썬][백준] 1668번: 트로피 진열  (0) 2020.05.31
[파이썬][백준] 1302번: 베스트셀러  (0) 2020.05.31
'파이썬/백준 문제' Related Articles more
Comments