ckdrb7067   4년 전

이분 그래프의 특성인 노드별로 색깔을 부여해서 같은 색깔과 연결되어 있으면 이분그래프가 될수 없다는걸 이용해서 풀고있습니다.

그런데 반례를 찾아봐도 정상적으로 나오는데 코드 어느부분이 잘못된건지 이해가 안되네요... 제가 이분그래프를 찾는 방법을 잘못 생각하고 있는 건지....


kyo20111   4년 전

반례 드리겠습니다.

ckdrb7067   4년 전

정답 NO 가 아닌가여..?
1(빨) 2(파)
4(빨) 3(파)
2(파) 3(파) 로
저는 정답이 NO라고 나오는데..

kyo20111   4년 전

1(빨) 2(파) 3(빨) 4(파) 로 색깔을 정해주면 됩니다.

제가 저 반례로 하고싶은 말은 입력받을때 색깔을 미리 정해놓는다는 것은 위험하는 것입니다.

ckdrb7067   4년 전

그런데 위 숫자 순서대로 1(빨) 2(파) 3(빨) 4(파) 로 하면 첫 케이스인 3일때

1(빨) 3(빨)

2(빨) 3(파) 에서

1(빨) 3(빨) 이 부분이 모순인거 같은데 이것만 따로 예외를 두어야하나요?

kyo20111   4년 전

처리해야할 경우가 너무나 많을것같아요 예외를 두는 방식으로 문제를 해결하면 풀수는 있을까합니다.

저같은 경우는 탐색을 할때 색을 입혀줌으로써 문제를 해결했습니다.

시작점부터 dfs를 할때 다음노드(거리가 1인노드)의 색을 현재 노드와 다른색을 입혀주는 방식으로요.

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