LeetCode - Is Graph Bipartite? 문제 보러가기

문제

문제 해결

일단 먼저 문제를 해석하면 무향 간선 그래프가 주어지고 해당 그래프가 이분 그래프인지를 묻는 문제다.

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html
이분 그래프가 무엇인지 알고 싶으면 위 링크를 확인...

쉽게 얘기하면 이분 그래프는 자신의 노드와 인접한 노드에 색을 칠한다고 가정할 때 인접한 노드는 무조건 다른 색이 칠해져있어야 한다.
해당 조건이 통과되면 이분 그래프가 된다.

사실 문제를 해석하고는 쉽게 풀 것이라고 생각했다.
0부터 시작해서 bfs를 통해 색을 칠하고 조건에 어긋나는 것이 있을 때 False를 반환하면 쉽게 풀릴 것이라고 생각했지만...
코드를 작성하면서 bfs라는 사실 망각하면서 풀어서 해결을 하지 못했다.

사실 말 그대로 bfs를 이용하면 된다.
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

위 예시를 사용해보자.
노드가 0번은 것은 1,2,3 모두 인접한다.
초기에는 색깔 배열을 모두 0으로 지정한다.
그러면 노드 0을 q에 담고 색깔[0]을 1로 나머지 인접한 노드들은 모두 -1로 색칠한 뒤 q에 담는다.(색깔 1,2,3번 노드 모두 -1로 색칠)
그다음은 노드 1을 검사한다. 1은 이미 -1로 색칠이 되어있기 때문에 인접한 0과 2의 색이 자신과 반대인 1인지 검사를 하면 된다. 그런데 색깔 1에서 1로 색칠이 아닌 -1로 되어있기 때문에(색깔 2 == 색깔 1 -> True) 바로 False를 반환하여 BFS를 종료한다.
이 모든 것이 통과되면(False가 반환되지 않고) True를 반환한다.

문제 해결 코드

from collections import deque

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [0] * n  

        for i in range(n):
            if color[i] != 0:
                continue
            queue = deque([i])
            color[i] = 1
            while queue:
                u = queue.popleft()
                for v in graph[u]:
                    if color[v] == 0:  
                        color[v] = -color[u]
                        queue.append(v)
                    elif color[v] == color[u]:  
                        return False
        return True