kk0640   4년 전

어디서 시간 오류가 나는건지 도저히 모르겠습니다..

plenilune   4년 전

연결요소들을 BFS로 탐색하신건가요?

그렇다면 이미 방문한 노드는 다시 방문하지 않아야합니다.

그러나 23행과 24행은 BFS로 "이미 탐색한" 노드를 시작점으로 "이미 탐색한" 노드들을 계속해서 불필요하게 BFS로 탐색하고 있는것 같네요.

이를 방지하기 위해서는, 방문하지 않은 노드만을 대상으로 BFS로 탐색해야 합니다.

보통은 visited를 표시할 자료형을 BFS 함수 밖에 두고, BFS가 끝나고 이미 방문한 노드들을 다시 방문하지 않도록 저장해놓아야 합니다.

그리고 방문하지 않은 노드들을 대상으로 BFS를 수행하시면 됩니다.

보통은 DFS로 많이들 구현하지만... 이 문제는 노드의 개수가 많지 않아서 BFS로도 통과가 가능할 것 같습니다.

결론은, 한번이라도 방문하지 않은 노드에 대해서만 BFS함수를 실행하시면 됩니다.

그러면 BFS함수가 1회전 할때마다(루트부터 너비를 우선하여 연결된 모든 노드들을 방문할 때마다) 연결요소의 개수가 하나씩 증가합니다.

왜냐하면 BFS 1회전은 연결요소 하나에 대해서만 실행이 되기 때문입니다.

그림을 직접 그려보시면 이해가 되실겁니다.

kk0640   4년 전

댓글 감사합니다. 말씀해주신대로 해도 잘 해결이 되지않아서 결국 dfs로 해결하였습니다. 

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