1707번 이분 그래프(DFS, 연결요소, DP) - ☆

#문제링크 : https://www.acmicpc.net/problem/1707

전략 : DFS를 수행하고 다음 노드와 현재노드를 구별하기 위해 check배열의 용도를 살짝 변경한다. 기존의 check배열은 방문 했다, 방문하지 않았다 만을 구별했지만, 이 문제에서는 두 집합으로 분류해야 하므로 check[node]값이 0이면 아직 방문하지 않은 노드, 1이면 색깔이 파랑인 노드, 2이면 색이 빨강인 노드라 생각하고 푼다. DFS를 수행할때, 다음 Depth의 노드와 현재 노드의 check값이 달라야 하므로, 1 + 2 = 3임을 이용하여 "3 - 현재노드 컬러 = 다음노드 컬러"로 점화식을 만들고 문제를 푼다.

※주의사항

1. 테스트 케이스 별로 벡터와 체크배열, 체크 변수등을 초기화 해주어야 한다.

2. 이분 그래프인지 확인할 때, 이미 방문한 배열은 다시 DFS를 수행할 필요가 없으므로 방문하지 않은 노드에만 DFS를 수행하여 시간복잡도를 줄인다.

Code