785. Is Graph Bipartite?

[zeikar]

Problem link

https://leetcode.com/problems/is-graph-bipartite/

Problem Summary

그래프가 이분 그래프인지 판단하는 문제.

Solution

먼저 이분 그래프의 정의를 보자.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

노드들을 A, B 두 덩어리로 나누었을 때 모든 간선은 A, B에 속한 노드들을 연결해야만 이분 그래프라고 한다.

코드로 생각해보면 탐색할 때 A, B 노드가 번갈아가며 나온다는 얘기가 된다. 즉, DFS, BFS 를 돌릴 때 A, B, A, B 같이 돌아가면서 나오면 이분 그래프라고 할 수 있다.
visited 배열에 해당 노드가 어디 속하는지 저장해두면서 탐색을 돌려주면 된다. 하나라도 아니면 바로 false를 반환하면 된다.
문제에서는 간선이 없는 노드가 있는데 이건 그냥 스킵해주면 된다.

Source Code

from collections import deque
from typing import List


class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        queue = deque()
        visited = [-1] * len(graph)

        for i in range(len(graph)):
            if not graph[i] or visited[i] != -1:
                continue

            queue.append((i, 0))
            visited[i] = 0

            while queue:
                node, flag = queue.popleft()

                for neighbor in graph[node]:
                    if visited[neighbor] == -1:
                        visited[neighbor] = 1 - flag
                        queue.append((neighbor, 1 - flag))
                    elif visited[neighbor] == flag:
                        return False

        return True