이 기사에서는 이분 그래프(Bipartite Graph)의 개념과 이를 판별하기 위한 알고리즘 문제를 다루겠습니다.
이분 그래프는 노드를 두 개의 집합으로 나눌 수 있는 그래프를 의미하며, 인접한 두 노드가 같은 집합에 속하지 않도록 할 수 있는지의 여부를 확인하는 것이 핵심입니다.
문제 설명
주어진 정점과 간선으로 이루어진 그래프의 이분 그래프 여부를 판별하는 문제를 해결해 보겠습니다.
구체적으로, 이 문제는 다음과 같은 입력을 받을 것입니다.
- 첫 번째 줄: 정점의 수
n과 간선의 수m이 공백으로 구분되어 주어집니다. - 다음
m개의 줄: 각 간선이 연결하는 두 정점u와v가 주어집니다.
출력으로는 주어진 그래프가 이분 그래프라면 YES, 아니라면 NO를 출력합니다.
예시 입력 1
3 3 1 2 2 3 1 3
예시 출력 1
NO
예시 입력 2
3 2 1 2 2 3
예시 출력 2
YES
문제 풀이 과정
1. 이분 그래프의 정의 이해하기
이분 그래프는 각 노드를 두 개의 그룹으로 나누었을 때, 같은 그룹의 노드끼리는 연결되지 않도록 할 수 있는 그래프입니다.
이러한 그래프는 일반적으로 이분색칠 가능성으로 판별할 수 있습니다.
즉, 어떤 노드를 색칠할 때, 인접한 노드들은 반대색으로 색칠되도록 하여 마지막까지 같은 색으로 색칠된 노드가 없으면 이분 그래프입니다.
2. 그래프 표현 방법
주어진 그래프를 표현하기 위해 인접 리스트를 사용할 것입니다. 각 정점에 대해 그 정점과 연결된 정점의 리스트를 유지합니다.
파이썬에서는 딕셔너리를 사용하여 그래프를 손쉽게 구성할 수 있습니다.
파이썬 코드 예시 (그래프 구성)
def create_graph(n, edges):
graph = {i: [] for i in range(1, n + 1)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
return graph
3. BFS 또는 DFS를 이용한 색칠하기
그래프를 탐색하기 위해 BFS나 DFS 알고리즘을 사용할 수 있습니다. 우리는 BFS 방식을 사용하여 이분 그래프 여부를 판별해보겠습니다.
BFS의 기본 아이디어는 시작 노드를 임의의 색으로 색칠하고, 인접한 모든 노드를 반대 색으로 색칠하며 진행하는 것입니다.
만약 어떤 인접한 노드가 이미 색칠되어 있고, 현재 색칠하려는 색과 같다면 이분 그래프가 아닙니다.
파이썬 코드 예시 (BFS 색칠하기)
from collections import deque
def is_bipartite(graph, n):
color = {}
for node in range(1, n + 1):
if node not in color:
queue = deque([node])
color[node] = 0 # 시작 노드를 색칠
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if neighbor not in color:
color[neighbor] = 1 - color[current] # 반대 색칠
queue.append(neighbor)
elif color[neighbor] == color[current]:
# 같은 색이면 이분 그래프가 아님
return False
return True
4. 전체 프로그램 구현
이제 그래프를 구성하고, 이분 그래프 판별 로직을 통합하여 전체 프로그램을 완성하겠습니다.
def main():
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
graph = create_graph(n, edges)
if is_bipartite(graph, n):
print("YES")
else:
print("NO")
if __name__ == "__main__":
main()
마무리
이번 글에서는 이분 그래프의 개념과 이를 판별하는 알고리즘 문제를 다루어 보았습니다.
BFS를 통해 효율적으로 이분 그래프를 판별할 수 있는 방법을 설명하였고, 파이썬 코드 예시를 통해 좀 더 실용적인 접근 방법을 살펴보았습니다.
앞으로도 다양한 알고리즘 주제를 다룰 예정이니, 계속해서 관심 가져주시기 바랍니다. 감사합니다!