[Leetcode] 785. Is Graph Bipartite?

⏱️ 소요시간

1시간. (문제를 이해하지 못하여 여러 번 읽고 이분그래프에 대한 다른 블로그 글을 보고 코드 작성함)

📚 문제 요약

[leetcode] 785. Is Graph Bipartite?
주어진 무방향 그래프가 이분그래프인지 판단하여 맞으면 True, 아니면 False를 리턴

📑 풀이 요약

이분그래프에 대해 알고 있다면 문제는 쉽게 풀 수 있다.
그래프의 노드의 집합을 둘로 나눴을 때, 집합에 속한 노드들은 서로 연결이 되지 않도록 나누는 경우가 존재한다면 해당 그래프는 이분그래프이다.

이분그래프인지 확인하는 방법은 실제로 내가 노드에 색을 칠해보면서 알 수 있다.

아래 그림을 보며 이분그래프인지 아닌지 판단하는 과정을 이해해보자.

이렇게 그래프 노드를 넓게 넓게 탐색해나가는 과정은 BFS이다. 큐를 이용하여 큐에 시작 노드를 넣어두고 큐가 빌 때까지 탐색해나가는 과정을 반복하면 된다. 모든 그래프의 노드를 탐색해야 하기 때문에 for 반복문을 이용한다.

💻 전체 코드

from collections import deque
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        checked = [0 for _ in range(n)]
        queue = deque([])
        for i in range(n):
            if graph[i] != [] and checked[i] == 0: #시작점을 담고
                queue.append([i, 1])
                checked[i] = 1                
                while queue: #bfs 시작
                    node, color = queue.popleft()
                    for k in graph[node]:
                        if checked[k] == color:
                            return False #이분그래프 아님
                        if checked[k] == 0:
                            queue.append([k, color*(-1)])
                            checked[k] = color * (-1)
        return True

💡 어려웠던 점

문제를 풀 때 당연히 0번 노드에 다른 노드가 연결되어있을 것이라 생각한 점은 반성해야 하며, (문제 예시만 그렇지 실제 테스트코드는 다를 수 있으니!) 그래프가 끊겨 있는 경우를 고려하지 않았다. (그래서 모든 노드를 탐색해야 한다)

😻도움을 받은 사이트

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html