문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
제한
-
2 ≤ K ≤ 5
-
1 ≤ V ≤ 20,000
-
1 ≤ E ≤ 200,000
풀이
이 문제는 개인적으로 상당히 어려웠다.
우선 이분 그래프가 무엇인지 모르는 상태였다.
이분 그래프(Bipartite Graph)란?
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.
즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는(<=> 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 한다.
이분 그래프의 특징
-
이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다.
-
이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 모조건 같은 색으로 칠해진다.
-
연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다.
-
모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.
이분 그래프 확인 방법
서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.
-
BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다.
-
다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다.
-
탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.
- BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다.
-
모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다.
-
이때 주의할 점은 연결 그래프와 비연결 그래프를 둘 다 고려 해야한다는 것이다.
- 그래프가 비연결 그래프인 경우 모든 정점에 대해서 확인하는 작업이 필요하다.
하지만 이러한 풀이방식을 처음부터 생각해 내기란 쉽지는 않다.
# BOJ 1707 골드 4
import sys
from collections import deque
# 정점(노드)들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서,
# 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다.
def bfs(v):
global visited
q = deque([v])
visited[v] = 1
while q:
cur = q.popleft()
for next in graph[cur]:
if visited[next] == 0:
visited[next] = visited[cur] * -1
q.append(next)
elif visited[next] == visited[cur]:
return False
return True
if __name__ == "__main__":
input = sys.stdin.readline
for _ in range(int(input())):
V, E = map(int, input().split())
graph = [[] for _ in range(V + 1)]
visited = [0] * (V + 1)
for _ in range(E):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1, V + 1):
if visited[i] == 0:
if bfs(i) == False:
print("NO")
break
else:
print("YES")