20183번 - 골목 대장 호석 - 효율성 2
다익스트라 대신 BFS를 이용하는 잘못된 코드가 통과됩니다. (채점번호 : 29279208)
BFS를 이용했을 때 최단거리가 아닌 데이터를 추가해주세요
진한님 좋은 반례 감사합니다 기능성 효율성 다 BFS로 접근했는데 잘못된 방식이었다는 걸 알았네요..
만약에 가진 돈(c)가 따로 주어지지 않았더라면 이분탐색 + BFS가 옳은 접근 방법이였을까요??? 아니면 C가 주어지는것과 상관없이 잘못된 접근일까요..?
경로의 가중치 합이 C원 이하여야한다는 제한이 없으면 시작 정점에서 도착 정점까지 도달이 가능한지 여부만 확인하면 되니 이분탐색 + BFS도 가능할 거 같습니다 :)
boj.kr/1800 이 문제가 C 제한이 없는 문젠데 이분탐색 + BFS로 풀리네요 ㅋㅋㅋㅋ
다른 문제도 알려주시고.. 감사합니다!!
재채점했습니다.
댓글을 작성하려면 로그인해야 합니다.
jinhan814 5년 전 2
다익스트라 대신 BFS를 이용하는 잘못된 코드가 통과됩니다. (채점번호 : 29279208)
BFS를 이용했을 때 최단거리가 아닌 데이터를 추가해주세요