문제 설명
문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
풀이 과정
문제만으론 정확히 어떤 경우에 이분 그래프인지 몰라서 더 찾아보았다.
요약해 보면, 색이 0과 1이 있고, a-b가 연결되어 있을때 a와 b의 색이 다르다 보면 된다.
- bfs를 활용한다.
- 현재 색이 0일때, 인접한 노드의 색을 1로 한다.
- 현재 색이 1일때, 인접한 노드의 색을 0으로 한다.
- bfs 진행 도중에 현재 색과 인접한 노드의 색이 같은 경우에는 이분 그래프가 되지 않는다.
- 전체 정점에 대해서 이분 그래프인 경우에는 True, 아닌 경우에는 False를 리턴한다.
소스 코드
import sys
from collections import deque
input = sys.stdin.readline
K = int(input().rstrip())
def bfs(graph, visited, start):
visited[start] = 0 # 시작 색은 0
queue = deque([[start, 0]])
while queue:
e, v = queue.popleft() # 현재 색깔
value = 1 if v == 0 else 0 # 현재 색깔 전환
for next_edge in graph[e]:
if visited[next_edge] == -1:
queue.append([next_edge, value])
visited[next_edge] = value
elif visited[next_edge] == v: # 다음 엣지의 색이 현재 색과 같으면 실패
return False
return True # 시작 정점에 대한 bfs 성공
for _ in range(K):
V, E = map(int, input().rstrip().split())
graph = [[] for _ in range(V+1)]
for __ in range(E):
a, b = map(int, input().rstrip().split())
graph[a].append(b)
graph[b].append(a)
visited = [-1] * (V+1)
answer = True
for i in range(1, V+1):
if visited[i] == -1:
if not bfs(graph, visited, i):
answer = False
break
if answer:
print("YES")
else:
print("NO")
'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글
[ 1660 ] [ DP ] 캡틴 이다솜 (0) | 2021.08.03 |
---|---|
[ 2629 ] [DP] 양팔저울 (0) | 2021.08.02 |
[ 1822 ] 차집합 (0) | 2021.08.01 |
[ 1918 ] [Stack] 후위 표기식 (0) | 2021.07.31 |
[ 4179 ] [BFS] 불! (0) | 2021.07.31 |