BOJ 1707: 이분 그래프

1차 시도

그래프의 정보를 실시간으로 입력 받으면서 이분 그래프가 성립하는지 판단하는 코드를 작성함

이분 그래프를 판단하는 방법인 노드를 RED, BLUE 두 가지 색을 각각 0과 1로 하였고, u 또는 w 번째 노드 중 하나만 색이 칠해져 있다면 반대 색을 BITWISE XOR 연산을 통해 저장하고, 연결되어있는 두 노드의 색이 같다면 “NO”를 출력하고 함수를 빠져나가고, 그렇지 않다면 “YES”를 출력하고 함수를 종료하는 코드를 짬

이 코드는 테스트 케이스에서는 맞으나 채점 할 때 6%에서 WRONG ANSWER를 받음

이후 실시간으로 검사하며 이 그래프가 이분 그래프임을 판단하는 알고리즘 대신 너비 우선 탐색(BFS)을 사용하여 문제를 해결하였다.

양방향 그래프를 입력하고, 각 노드의 방문처리를 위해 visited라는 벡터에 -1의 값으로 초기화했다.

1~v번째 노드를 돌면서 각 노드가 방문하지 않은 노드라면 각 노드에서 시작하는 BFS를 돌리고 마찬가지로 색을 BITWISE XOR로 칠하였다.

이후 right()라는 함수를 이용해 이 그래프가 이분 그래프임을 만족하는지 판단하여 맞다면 “YES”, 틀리다면 “NO”를 출력하도록 하였다.