dlgldgld   1년 전

해당 문제는 ST에서 ED로 도달할 수 있는 모든 경로에 대해서 계산이 이뤄져야하는 것으로 이해했습니다.
허나 BFS는 모든경로를 탐색할 수 없는 것으로 알고 있습니다. 그럼에도 불구하고 BFS를 통해 문제를 많이 해결하셨던데 어떻게 이것을 통해 답을 구할수 있을거라 확신할 수 있는지 기준을 알고싶습니다.

중량을 기준으로 파라메트릭 서치 + BFS를 했을때 모든 경로의 케이스에 대해서 답을 찾을 수 있다는 증명은 어떻게 할 수 있나요?
아래 예시를 기준으로 BFS로 경로를 탐색할때 체크하지 못하는 경우가 있는 것 같은데요.. 이런 것들을 제외하고도 최적화된 답을 찾을 수 있다고 어떻게 검증을 할까요?

1. input
6 9
1 2 5
1 4 5
1 3 1
4 3 1
4 2 5
3 5 4
2 5 4
2 6 2
5 6 2
1 3

2. flow 
1) 1->2, Queue 2
2) 1->4, Queue 2, 4
3) 1->3, Queue 2, 4, 3
4) 1->2->5  (pop) Queue 4,3 -> visited[2] = True
5) pop 이후 4번 탐색 => 4->2 경로는 이미 visited[2]가 true 이므로 체크하지 않음.
    => 1->4->2 경로는 탐색하지 않음.


leeh18   1년 전

이 문제의 이분 탐색 풀이의 경우 시작 지점에서 출발해서 도착 지점으로 도달할 수 있는지를 판단해 주어야 합니다. 도달 가능성을 판단하기 위해서 가능한 모든 경로를 확인할 필요는 없으므로 BFS, DFS, 분리 집합 모두 유효한 풀이가 될 것입니다 :)

dlgldgld   1년 전

이해했습니다! 답변 감사합니다!! 

댓글을 작성하려면 로그인해야 합니다.