knc0827   4년 전

메모리 부분에서 놓치고 있는게 있는거 같은데 잘 모르겠습니다.

kwakws0627   4년 전

bfs 함수는 한 번 방문한 정점은 다시 방문하지 말아야 합니다.

bfs 함수 시작할 때

cout << "start : " << start << "\n;

위 코드를 추가하고 확인해보세요.

계속 1번 3번 노드만 무한히 반복 방문합니다.

(그리고 위 방법은 bfs 가 아니고 dfs 입니다.)

또한, 위 코드는 올바른 풀이 방법이 아닌 듯 합니다.

bfs 코드 안에서 지금 방문 중인 정점 다음 노드와 색깔이 같으면 이분그래프가 아니라고 바로 판단할 수 있어야 합니다.

kwakws0627   4년 전

조금 정정하겠습니다.

cout << "start : " << start << "\n;

위 코드를 추가하고 예제를 실행해보면

계속 1, 3번 노드만 무한히 반복 방문하고 있습니다.

(무한 반복 방문이 메모리 초과의 오류인지는 잘 모르겠지만 확실히 무한 반복 방문이 문제가 되는건 맞습니다.)

그리고 bfs 함수(사실은 dfs가 되어야 맞습니다.) 안에서 현재 방문중인 노드 start 와

다음 방문 예정인 next 노드의 색깔이 같으면 이분 그래프가 아니라고 바로 판단해야 합니다.

위 코드처럼 전부 칠한 다음에 bfs 함수가 끝나고 solve 함수로 판단하려고 하면

bfs 함수 안에서 이미 칠해진 노드를 다른 색깔로 덧칠해버릴 수 있어서

solve 함수가 잘못된 결과를 내놓을 수 있습니다.

knc0827   4년 전

아 맞습니다 dfs로 풀고 있었는데 잘못 기입했네요

즉각적으로 검사할 수 있어야 하는군요

고치고 다시 이 게시글 수정하겠습니다

감사합니다

knc0827   4년 전

이분 그래프 정의대로 그냥 칠하고 다시 검사하는 식으로 풀었습니다

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