[785] Is Graph Bipartite? | LeetCode Medium

🔎 문제설명

바로 한글 요약

주어진 그래프가 이분 그래프라면 True, 아니면 False를 반환하기

Example 1

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false

Example 2

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true

제한사항

• graph.length == n
• 1 ≤ n ≤ 100
• 0 ≤ graph[u].length < n
• 0 ≤ graph[u][i] ≤ n - 1
• graph[u] does not contain u.
• All the values of graph[u] are unique.
• If graph[u] contains v, then graph[v] contains u.

---

⚗️ 이분 그래프란?

이분그래프가 뭔지만 알면 이문제는 쉽게 풀 수 있습니다.

이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠한다고 가정했을때 두가지 색을 기준으로 두 그룹으로 나눌 수 있고 서로 다른 그룹의 정점이 간선으로 연결된 그래프입니다.

이해가 안될까봐 그림을 넣어 드렸습니다.

위에 1번 예제그래프에 색을 칠해보면 왜 False인지 쉽게 알 수 있습니다.

이분그래프를 해결할 때 일반적으로 BFS/DFS로 풉니다.

이미지 출처 : https://sanghoon9939.tistory.com/33

---

🧊 파이썬 코드

🌓 BFS

from collections import deque
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        check = [-1]*len(graph) #방문 체크
        
        for i in range(len(graph)): #BFS
            Q = deque([])
            if check[i] == -1:
                Q.append(i)
                check[i] = 0
            while Q:
                n1 = Q.popleft()
                for n2 in graph[n1]:
                    if check[n2] == -1:
                        check[n2] = (check[n1] + 1)%2 # 1 or 0만 나옴
                        Q.append(n2)
                    elif check[n1] == check[n2]:
                            return False
        
        return True

🌗DFS

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        colors = {}
        for n in range(len(graph)):
            if n not in colors and not self.dfs(graph, n, colors, 1):
                return False

        return True

    def dfs(self, graph, node, colors, color):

        colors[node] = color

        for node_to in graph[node]:
            if node_to in colors:
                if colors[node_to] == colors[node]:
                    return False
            elif not self.dfs(graph, node_to, colors, color * -1): #1 or -1만 나옴
                    return False

        return True