백준 1707번 : 이분 그래프 in Python
이 문제는 그래프가 주어질 때 이 그래프가 이분 그래프인지를 판단하는 문제로, 여기서 이분 그래프란 그래프의 정점의 집합을 서로 인접하지 않는 정점들의 집합 두 개로 분할할 수 있는 그래프를 말한다.
이분 그래프인지를 판단하기 위해서는, 각 정점들을 두 집합에 넣으면서 집합 안에 있는 정점들끼리 인접하지 않는지 확인해야 한다. 이를 매번 확인하기에는 시간이 오래 걸리므로, 대신 정점을 집합에 하나 넣고 그 정점과 인접한 점들은 그 정점이 들어있는 집합과 다른 집합에 넣는 방법을 생각해 볼 수 있다. 그러면 적어도 그 정점과 인접한 점들이 정점이 들어있는 집합에 들어오지는 않을 것이다. 이러한 방식으로 나머지 점들에 대해서도 그 점들과 인접한 점들을 다른 집합에 넣어 두 개의 정점의 집합을 만들 수 있다.
하지만 이 과정을 반복하다보면 집합에 이미 들어있는 정점들끼리 인접하는 경우가 발생할 수 있는데, 그러한 경우 인접하는 두 정점 중 어떠한 점도 다른 집합으로 옮기면 그 점이 해당 집합으로 오게 된 원인인 정점과 같은 집합에 오게 된다. 그러므로 두 정점 모두 다른 집합으로 옮길 수 없고, 따라서 해당 그래프는 이분 그래프가 아니라는 결론을 얻게 된다. 이러한 방식으로 해당 그래프가 이분 그래프인지 판별하면 된다.
이를 코드로 직접 구현하기 위해서는, 우선 모든 정점들에 대해 그 정점들과 인접한 모든 점들을 순회하며 다른 집합으로 보내고, 그 점들에 대해 같은 과정을 반복하므로 각 정점들에 BFS를 적용해야 한다. 그리고 이미 방문한 정점들이나, 인접한 정점이 없는 정점들은 BFS를 실행하지 않아도 되므로 스킵한다. 나머지 과정은 일반적인 BFS 과정을 따르나 다만 서로 인접한 정점들은 다른 집합에 넣어야 하므로 visit 배열의 각 entry를 해당 인덱스의 정점이 집합 1과 집합 2 중 어떤 집합에 들어있는지를 나타낸다고 한다. 즉, 만약 어떤 정점이 집합 1(집합 2)에 들어있고 그 정점과 인접한 점들 중 방문하지 않은 점들이 있을 경우 그 점들을 집합 2(집합 1)에 넣는다. 만약 그 정점과 인접한 점들 중 이미 방문한 점이 해당 정점과 같은 집합에 들어있다면 이분 그래프를 만들 수 없으므로 기존에 True로 지정해둔 이분 그래프 가능 여부를 나타내는 변수를 False로 하고 모든 loop를 빠져나온다.
그러면 만약 모든 정점들을 정상적으로 두 집합으로 나누는데 성공한 경우 이분 그래프 가능 여부 변수가 True일 것이므로 "YES"를 출력하고, 그렇지 않은 경우 "NO"를 출력한다.
이를 코드로 구현하면 다음과 같다.
import sys
from collections import deque
K = int(input())
for _ in range(K):
V, E = map(int, input().split())
# 그래프를 표현하기 위한 배열
graph = [[] for _ in range(V+1)]
for _ in range(E):
v1, v2 = map(int, input().split())
graph[v1].append(v2)
graph[v2].append(v1)
# 각 인덱스에 해당하는 정점이 어느 집합에 들어있는지를 나타내는 배열
visit = [0 for _ in range(V+1)]
queue = deque()
# 이분 그래프인지를 나타내는 변수
Bipartite = True
# 그래프의 각 정점에 대해 순회한다.
for i in range(1, V+1):
# 해당 정점과 인접한 정점이 없거나 이미 방문한 정점인 경우 BFS를 스킵한다.
if len(graph[i]) == 0 or visit[i] > 0: continue
queue.append(i)
# 우선 정점을 집합 1에 넣는다.
visit[i] = 1
while len(queue) > 0:
v = queue.popleft()
for w in graph[v]:
# 정점 v가 집합 1에 있고 정점 w를 아직 집합에 넣지 않은 경우
# w를 집합 2에 넣는다.
if visit[v] == 1 and visit[w] == 0:
visit[w] = 2
queue.append(w)
# 정점 v가 집합 2에 있고 정점 w를 아직 집합에 넣지 않은 경우
# w를 집합 1에 넣는다.
elif visit[v] == 2 and visit[w] == 0:
visit[w] = 1
queue.append(w)
# 정점 v와 w가 같은 집합에 들어있는 경우
# Bipartite 변수를 False로 바꾸고 모든 loop를 빠져나온다.
elif visit[v] == visit[w]:
Bipartite = False
break
if not Bipartite:
break
if not Bipartite:
break
# 이분 그래프인 경우
if Bipartite:
print("YES")
# 이분 그래프가 아닌 경우
else:
print("NO")