hwy16016   1달 전

bfs하면서 adj노드탐색할 때 번갈아가며 set a, b에 넣어주면서 중복확인을 했습니다.

어떤 문제일까요?

hwy16016   1달 전

해결했습니다.

visited로 탐색했는지만 보면 bfs에서 탐색한 노드에 도착했을 때 이 노드가 a에 속했는지 b에 속했는지 알수가 없는데 

f로 a/b 번갈아가며 계속 넣었기 때문에

길이가 홀수인 사이클이 그래프에 있게되면 a에 속한 노드의 인접노드들을 다시 a에 넣게 되어 틀린답이 나왔습니다.

visited배열의 내용을 0/1이 아닌 0/1/-1로 바꿔서 해결했습니다.

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