백준 1707번 : 이분그래프
난이도 : 골드 4
- 문제 소개
- 조건
- 테스트 케이스 K는 2 이상 5 이하이다.
- 정점의 개수 V는 1 ~ 20000개이다.
- 간선의 개수 E는 1 ~ 200000개이다.
- 코드
import sys
input = sys.stdin.readline
from collections import deque
K = int(input())
def bfs(graph, start):
q = deque()
q.append(start)
if visited[start] == 0:
visited[start] = 1
while q:
v = q.popleft()
color = visited[v]
for i in graph[v]:
if visited[i] == 0:
q.append(i)
if color == 1:
visited[i] = 2
else:
visited[i] = 1
elif visited[i] == 1:
if color == 1:
print("NO")
return False
elif visited[i] == 2:
if color == 2:
print("NO")
return False
return True
for i in range(K):
flag = 0
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 k in range(1, V + 1):
if not bfs(graph, k):
flag = 1
break
if flag == 0:
print("YES")- 해설
이 문제는 dfs와 bfs 어느 것을 사용해도 문제가 없습니다. 저는 bfs로 해결했는데요, 먼저 너비우선탐색 부분을 보기 전에 플러드 필 부분을 확인하겠습니다. flag, graph, visited를 정의해주었습니다. 그리고
for k in range(1, V + 1):
if not bfs(graph, k):
flag = 1
break
if flag == 0:
print("YES")이 부분이 중요한데요, 만약 정점 중에서 연결되지 않는 정점이 있으면, 너비 우선 탐색으로는 찾을 수 없으므로 for문을 통해 완전 탐색을 시행해줍니다. 그리고 찾다가 만약 bfs가 True를 리턴하지 않는 부분을 발견하면 flag를 1로 바꾸어주고 for문을 탈출합니다.
이제 bfs 부분을 확인해볼까요? 처음엔 q라는 queue에 처음 들어갈 수를 넣어주고, 이 부분을 방문했다고 체크해줍니다. 그리고 while문을 들어가게 됩니다. v는 q에 저장된 가장 왼쪽 수를 뺀 것이며, color를 visited[v]로 저장해줍니다. 그리고 graph[v]에 연결된 정점들을 확인해줍니다. 확인한 위치가 방문한 적이 없다면 q에 이 위치를 넣어주고, color가 1이면 2를, 2면 1을 저장해주어서 인접한 위치와 다른 색을 가지도록 해줍니다. 근데 만약 이 위치를 방문한 적이 있으면( visited[v] == 1 or visited[v] == 2) color를 확인해서 같은 숫자면 False를 리턴해주어서 이 그래프가 이분되지 않음을 증명해줍니다.
