소스코드
import sys
from collections import deque
input = sys.stdin.readline
K = int(input().strip()) # 테스트 케이스 수
# 탐색하며 이분 그래프인지 아닌지 판별하는 함수
def bfs(graph, group, node):
queue = deque([node])
while queue:
now = queue.popleft()
# 인접노드 확인
for neighbor in graph[now]:
if group[neighbor] == None:
group[neighbor] = 1 - group[now]
queue.append(neighbor)
elif group[neighbor] == group[now]:
# 방문했던 노드가 인접노드와 색깔까지 동일하다면 -> 이분 그래프 X
return False
return True
for _ in range(K):
V, E = map(int, input().strip().split())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
u,v = map(int, input().strip().split())
graph[u].append(v)
graph[v].append(u)
result = "YES"
group = [None] * (V + 1)
for i in range(1, V + 1):
if group[i] == None:
if not bfs(graph, group, i):
result = "NO"
break
print(result)
Python
복사
풀이
그래프를 그려 RB트리를 색칠하는 것처럼 하나하나 노드의 색깔을 입혀보다보면, 예제 입력1에서 2번째 케이스에 대해 NO가 나온다는 것을 눈으로 확인할 수 있습니다. AI에게 물어보니 홀수 개의 사이클이 형성되면 이분 그래프가 될 수 없다고 하더라구요. 아무튼 그냥 색깔을 반전시키며 다음 노드로 진출하다가 인접 노드끼리 색이 동일하면 이분 그래프가 될 수 없다는 것을 확인할 수 있습니다.
•
처음에는 단순하게 큐의 원소로 (노드 번호, 색깔)을 넣어서 이전 노드와만 색깔을 비교하는 형태로 사용하려고 했습니다. 왜 그랬을까요? 이전 노드와만 비교해야하는게 아니라 모든 인접노드와 비교해야하는데 말입니다.
◦
전체 노드들의 색깔 정보를 포함한 group 리스트를 생성합니다.
•
연결 그래프(특정한 두 정점이 꼭 이어져있으리라 보장되는 그래프)가 아닐 수도 있음을 주의해야합니다. 그래서 모든 노드를 순회하면서 아직 그룹이 결정되지 않은(=방문하지 않은) 노드에 대해서 BFS 함수를 실행해 그룹을 지정하고 이분 그래프를 만들어내는지 체크합니다.
◦
bfs함수의 결과가 True면 계속해서 다음 노드를 탐색합니다.
◦
bfs함수의 결과가 False면 이분그래프가 아니라는 소리이므로 곧바로 반복문을 종료하고 결과를 “NO”로 수정합니다.
•
BFS 함수는 다음 과정을 갖습니다 :
◦
현재 노드의 인접 노드를 확인합니다
▪
만약 방문한 적 없는 인접 노드라면(그룹이 지정된 적 없다면), 현재 노드의 그룹과 반대 그룹으로 지정하고 큐에 삽입합니다.
▪
만약 방문한 적 있는 인접 노드라면(그룹이 지정된 적 있다면), 현재 노드의 그룹과 동일한지 확인합니다
•
만약 인접 노드와 현재 노드의 그룹이 동일하다면 이분 그래프가 아니라는 소리입니다.
•
결과 출력하면 끝!!
회고
•
아직 자료구조를 뭘 써야겠다를 확신을 갖고 사용한다는 느낌을 잘 못 받는 경우가 왕왕 있다고 생각합니다. 왜 그럴까요? 지속적으로 복기해보면서 특정 상황에 대해 어떤 자료구조를 기반으로 풀어내야겠다는 감각을 늘려나가야할 듯 합니다.