https://leetcode.com/problems/is-graph-bipartite/description/
문제 파악
주어진 문제는 무방향 그래프가 주어졌을 때, 그 그래프가 노드를 두 개의 독립된 집합으로 나눌 수 있는 이분 그래프(bipartite graph)인지 확인하는 문제다.
그래프는 노드 번호가 0부터 n-1까지 부여된 노드들로 구성되고 graph라는 2차원 배열이 주어지며 graph[u]는 노드 u와 인접한 노드들의 리스트다.
당연히 무방향 그래프이기 때문에 v가 graph[u]에 있다면 u도 graph[v]에 있다.
이렇게 코드를 통해 그래프가 이분 그래프인지를 확인하고 이분 그래프이면 true를 반환해주면 된다.
접근 방법
그래프가 이분 그래프인지 확인하는 방법 중 하나는 BFS나 DFS를 이용하여 그래프를 2색으로 칠하는 것이다. 만약 인접한 노드가 같은 색으로 칠해져야 하는 상황이 발생하면, 그 그래프는 이분 그래프가 아니다.
코드 구현
from collections import deque
class Solution:
def isBipartite(self, graph):
n = len(graph)
color = [-1] * n # -1은 아직 칠해지지 않은 노드를 의미
def bfs(start_v):
q = deque([start_v])
color[start_v] = 0 # 시작 노드를 0으로 칠함
while q:
cur_v = q.popleft()
for next_v in graph[cur_v]:
if color[next_v] == -1: # 아직 칠해지지 않은 경우
color[next_v] = 1 - color[cur_v] # 다른 색으로 칠함
q.append(next_v)
elif color[next_v] == color[cur_v]: # 이미 같은 색으로 칠해진 경우
return False # 이분 그래프가 아님
return True # 해당 컴포넌트가 이분 그래프임
for i in range(n):
if color[i] == -1: # 아직 방문하지 않은 노드에 대해 BFS 시작
if not bfs(i):
return False # 이분 그래프가 아님
return True # 모든 컴포넌트가 이분 그래프임