[BOJ/백준] 1707. 이분 그래프 (python)

https://www.acmicpc.net/problem/1707

Problem

이분 그래프란, 인접한 노드를 서로 다른 색으로 칠할 때 그래프 내에 모든 노드를 두가지 색으로만 칠할 수 있는 노드이다.

주어진 그래프가 이분 그래프인지 아닌지를 판단하는 문제
​

Solution

dfs를 이용했다.

두가지 색을 이용해 노드들을 칠해야하는데 교차로 색을 칠해주기 위해 -1과 1을 이용해 교차로 값을 부여해주었다.

인접한 노드들을 리스트에 저장해준 뒤, 방문한 적 없는 노드들만 검사해준다.

인접 노드들을 -1과 1을 번갈아가며 저장하다가 모든 노드를 방문했을 때,

인접 노드가 같은 색이면 false를 반환해준다.

함수가 모두 끝났을 때 false를 반환하지 않으면 모든 노드들을 이분화 시킨것이다.
​

Python Code