1707번: 이분 그래프
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수
www.acmicpc.net
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
우선 이 문제를 풀기 전에 이분 그래프의 대한 의미를 집고 넘어가야겠다.
이분 그래프는 위의 그림처럼 인접한 노드를 다른 색으로 칠했을 때 두 가지 색으로 표현 가능한 그래프를 말한다.
대충 감이 오지 않는가?
본인은 BFS를 활용하여 문제를 해결하였고 DFS로도 해결 가능할 것으로 보인다.
해결 방법
간선 정보를 저장할 배열과 방문 여부를 저장할 배열, 두 개를 선언한다.
양방향 탐색이 필요하므로 간선 정보를 저장할 때 양방향으로 저장해준다.
이후 BFS를 통해 탐색을 진행하는데 인접한 노드를 방문하면 현재 노드와 다른 색(?)으로 칠해주는 것이 핵심이다.
1. 현재 노드를 1로 설정하고 인접한 노드가 방문하지 않은 경우 인접한 노드를 -1로 설정한다.
(1 : RED, -1 : BLUE라고 생각하면 이해하기 쉬울 것이다.)
2. 이미 방문한 노드인 경우 현재 노드와 인접한 노드의 합을 구해서 0이 아닌 경우는 이는 이분 그래프가 아니라는 것을 나타낸다.
(ex 현재 노드의 색 = 1, 인접한 노드의 색 = 1 -> 합하면 2 -> 이분 그래프가 아님.)
3. 모든 노드에 대해 위 과정을 반복한다.
코드로 나타내면 아래와 같다.
이렇게 하고 실행을 돌렸는데
구현 방법은 문제가 없어보였다. 결국 반례를 찾지 못하고 질문 게시판을 참고했더니 적절한 반례가 있었다.
나는 문제를 해결할 때 모든 간선이 연결되어 있다고 생각하였고 BFS를 한 번만 탐색하도록 코드를 구현했었다.
하지만 아래 그림과 같은 그래프도 결국 이분 그래프가 될 수 있다는 것을 인지하지 못했다.
이후 그래프가 나눠진 경우에도 탐색을 할 수 있도록 코드를 추가하였고 해결할 수 있었다.
파이썬으로 구현한 코드이다.
주석 처리한 부분이 위에서 말한 반례도 통과할 수 있도록 추가한 코드이다.
C++로 구현한 코드이다.
언어 2개 정도는 능숙하게 써야한다고 생각해서 C++로도 구현하고 있는데 확실히 파이썬이 쉬운 것 같다.
"문제 읽고 파이썬으로 해결하는 시간 =< C++로 다시 구현하는 시간" 약간 이렇다...
'✍️ 코테 준비 > DFS, BFS' 카테고리의 다른 글
[BFS][Kotlin] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기 (0) | 2022.03.20 |
---|---|
[DFS와 BFS] [Python / C++] 1260. DFS와 BFS (0) | 2021.04.18 |
[DFS와 BFS] [Python / C++] 1707. 이분 그래프 (0) | 2021.04.14 |
[DFS와 BFS] [Python / C++] 7562. 나이트의 이동. (0) | 2021.04.13 |
[DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기. (0) | 2021.04.12 |