1939번 - 중량제한
읽어 주셔서 감사합니다^^
우선 저의 접근 법을 말씀드리면 일단 힌트를 얻어 이분탐색과 BFS를 이용하였습니다.
입력으로 들어오는 (간선들의 가중치) 중량들의 최대값을 얻어서 1부터 c의 최고값
left = 1, right = 다리의 중량들의 최대값
이 사이에서 이분탐색을 실시 하였습니다.
중량 제한인 . 즉 mid 값으로 start 부터 해서 end 까지 목적지로 도착 할 수 있는가를 bfs 로 구현 하였습니다.
도달 할 수 있다면 - > left = mid + 1 도달 가능 하니깐 범위를 큰값으로 옮길 수 있으므로.
도달 할 수 없다면 - > right = mid - 1 도달 할 수 없으니 좀더 작은 범위를 탐색을 해야하므로.
범위를 제한 하여 탐색범위를 나누 었습니다.
이렇게 시도 했지만 7% 에서 틀렸습니다라고 나옵니다
혹시 제가 접근을 잘못한건지 아니면 소스코드에서 오류가 있는건지 도와 주세요ㅠ
댓글을 작성하려면 로그인해야 합니다.
axa1239 4년 전
읽어 주셔서 감사합니다^^
우선 저의 접근 법을 말씀드리면 일단 힌트를 얻어 이분탐색과 BFS를 이용하였습니다.
입력으로 들어오는 (간선들의 가중치) 중량들의 최대값을 얻어서 1부터 c의 최고값
left = 1, right = 다리의 중량들의 최대값
이 사이에서 이분탐색을 실시 하였습니다.
중량 제한인 . 즉 mid 값으로 start 부터 해서 end 까지 목적지로 도착 할 수 있는가를 bfs 로 구현 하였습니다.
도달 할 수 있다면 - > left = mid + 1 도달 가능 하니깐 범위를 큰값으로 옮길 수 있으므로.
도달 할 수 없다면 - > right = mid - 1 도달 할 수 없으니 좀더 작은 범위를 탐색을 해야하므로.
범위를 제한 하여 탐색범위를 나누 었습니다.
이렇게 시도 했지만 7% 에서 틀렸습니다라고 나옵니다
혹시 제가 접근을 잘못한건지 아니면 소스코드에서 오류가 있는건지 도와 주세요ㅠ