[DFS와 BFS] [Python / C++] 1707. 이분 그래프

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

 

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

---

우선 이 문제를 풀기 전에 이분 그래프의 대한 의미를 집고 넘어가야겠다.

출처 : https://gmlwjd9405.github.io

 

이분 그래프는 위의 그림처럼 인접한 노드를 다른 색으로 칠했을 때 두 가지 색으로 표현 가능한 그래프를 말한다.

 

대충 감이 오지 않는가?

 

본인은 BFS를 활용하여 문제를 해결하였고 DFS로도 해결 가능할 것으로 보인다.

 

해결 방법

간선 정보를 저장할 배열과 방문 여부를 저장할 배열, 두 개를 선언한다.

양방향 탐색이 필요하므로 간선 정보를 저장할 때 양방향으로 저장해준다.

이후 BFS를 통해 탐색을 진행하는데 인접한 노드를 방문하면 현재 노드와 다른 색(?)으로 칠해주는 것이 핵심이다.

 

1. 현재 노드를 1로 설정하고 인접한 노드가 방문하지 않은 경우 인접한 노드를 -1로 설정한다.

(1 : RED, -1 : BLUE라고 생각하면 이해하기 쉬울 것이다.)

 

2. 이미 방문한 노드인 경우 현재 노드와 인접한 노드의 합을 구해서 0이 아닌 경우는 이는 이분 그래프가 아니라는 것을 나타낸다.

(ex 현재 노드의 색 = 1, 인접한 노드의 색 = 1 -> 합하면 2 -> 이분 그래프가 아님.)

 

3. 모든 노드에 대해 위 과정을 반복한다.

 

코드로 나타내면 아래와 같다.

 

 

이렇게 하고 실행을 돌렸는데

???

 

구현 방법은 문제가 없어보였다. 결국 반례를 찾지 못하고 질문 게시판을 참고했더니 적절한 반례가 있었다.

나는 문제를 해결할 때 모든 간선이 연결되어 있다고 생각하였고 BFS를 한 번만 탐색하도록 코드를 구현했었다.

하지만 아래 그림과 같은 그래프도 결국 이분 그래프가 될 수 있다는 것을 인지하지 못했다.

 

적절한 반례

 

이후 그래프가 나눠진 경우에도 탐색을 할 수 있도록 코드를 추가하였고 해결할 수 있었다.

 

파이썬으로 구현한 코드이다.

주석 처리한 부분이 위에서 말한 반례도 통과할 수 있도록 추가한 코드이다.

 

 

C++로 구현한 코드이다.

 

 

언어 2개 정도는 능숙하게 써야한다고 생각해서 C++로도 구현하고 있는데 확실히 파이썬이 쉬운 것 같다.

"문제 읽고 파이썬으로 해결하는 시간  =<  C++로 다시 구현하는 시간"  약간 이렇다...