반응형
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 활용문제.
start지점과 end지점이 이미 정해져 있으므로, BFS에서는 'start -> end'로 이동하는 모든 경로에 weight 제한에 통과하는지 아닌지를 검사해야 한다.
이분탐색으로 무게를 찾으면서 '해당 무게로 이동할 때 start -> end까지 도착이 가능한지'를 검사하는 방식으로 최대 중량을 찾아내는 방식,
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 거스름돈 (Level 3) (1) | 2020.01.01 |
|---|---|
| [Python] 백준 14501. 퇴사 (0) | 2019.12.31 |
| [Python] 백준 1149. RGB거리 (0) | 2019.12.28 |
| [Python] 프로그래머스. 가장 큰 정사각형 (Level 2) (0) | 2019.12.26 |
| [Python] 프로그래머스. 구명 보트 (Level 2) (0) | 2019.12.25 |