leetcode : Is Graph Bipartite?

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

Is Graph Bipartite? - LeetCode

 

인접한 노드는 다른 그룹에 속해있어야 된다. 이때 총 그룹의 개수가 2개가 될 수 있는지 알아내는 문제다.

컬러칠하기 문제와 비슷하다.

 

일단 union find로 한번 풀어봤다.

아무 노드랑도 연결되지 않은 외딴 섬을 제외하고 나머지 중에 그래프가 총 몇 개 있는지, 그 그래프 내에서 생성되는 그룹의 수는 몇개인지를 구해서 총그룹개수/그래프수 == 2가 되는지 확인한다.

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        vertexgroup = [i for i in range(len(graph))]
        graphgroup = [i for i in range(len(graph))]
        vcount = len(graph)
        gcount = len(graph)
        
        def find(x, group):
            if x != group[x]:
                group[x] = find(group[x], group)
            return group[x]
        
        def union_vertex(x, y):
            nonlocal vcount
            
            if x > y:
                x,y = y,x
                
            r1 = find(x, vertexgroup)
            r2 = find(y, vertexgroup)
            
            if r1 != r2:
                vcount -=1

            vertexgroup[r2] = r1

        def union_graph(x, y):
            nonlocal gcount
            
            if x > y:
                x,y = y,x
                
            r1 = find(x, graphgroup)
            r2 = find(y, graphgroup)
            
            if r1 != r2:
                gcount -= 1
            
            graphgroup[r2] = r1
            
        for v in range(len(graph)):
            if graph[v]:
                for i in range(len(graph[v]) - 1):
                    union_vertex(graph[v][i], graph[v][i+1])
                    union_graph(v, graph[v][i])
                union_graph(v, graph[v][-1])
            else:
                vcount -= 1
                gcount -= 1
                
        return vcount / gcount == 2 if gcount else True

예상했던 결과다.

 

컬러칠하기로 풀어봤다

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0] * len(graph)
        
        def dfs(v, c):
            if not color[v]:
                color[v] = c
                return all(dfs(nxt, 1 if c==2 else 2) for nxt in graph[v])
            return color[v] == c
            
        return all(dfs(v,1) for v in range(len(graph)) if not color[v])