그래프 (이분 그래프)

그래프를 따라 번갈아가면서 색을 칠하다가 이미 방문했던 정점이 이전 정점 색과 같은 색이라면 이분그래프가 아니다.

색은 dfs 함수에서 group과 -group을 번갈아 넘겨주면서 1과 -1로 표현한다.

 

result를 True로 선언 하고 dfs 함수에서 만약 정점의 색이 같다면 False를 리턴해 result에 저장

 

마지막에 result의 값에 따라 이분그래프 판별 출력

 

 

*주의* 재귀 함수 dfs에서 return을 했을 때 현재 돌고있는 함수만 종료 된것이지 dfs함수 전체가 종료되는 것이 아니다. 

처음 계획했던 dfs함수

 

return False를 하더라도 종료되는 것은 dfs의 전체 과정이 아니라 딱 현재 실행되고 있는 함수뿐이다. 처음에 전역에서 호출된 dfs와 그 dfs가 호출한 dfs는 서로 다른 함수이며, 그 dfs가 호출한 dfs도 또 다른 함수이다.

예를 들어 1에서 시작한 dfs가 2로 들어갔는데 2에서 False를 반환했다고 하더라도 1도 False를 반환하는 것은 아니며, 이와는 전혀 상관없이 1은 계속해서 탐색을 진행한 뒤 True를 반환할 수 있습니다. 그렇게 되면 최종적으로 본 코드 34번째 줄에 반환되는 것은 True가 된다