- Problem

785. Is Graph Bipartite?

- 내 풀이 (BFS)

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        NOT_COLORED = 0
    
        def bfs(node):
            q = deque([node])
            nodes[node] = 1

            while q:
                cur = q.popleft()

                for nei in graph[cur]:
                    if nodes[nei] == NOT_COLORED:
                        nodes[nei] = -nodes[cur]
                        q.append(nei)
                    elif nodes[nei] == nodes[cur]:
                        return False
            
            return True

        nodes = [NOT_COLORED] * len(graph)

        for node in range(len(graph)):
            if nodes[node] == NOT_COLORED:
                if not bfs(node):
                    return False

        return True

- 결과