<Medium> Is Graph Bipartite? (LeetCode : C#)

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

📕 문제 설명

n개의 노드를 가지는 무방향 그래프가 주어질 때, 그래프의 bipartite 여부 반환

bipartite는 2개의 독립 set A, B에 각 set의 모든 노드에 대해 간선이 연결되는 경우를 말한다. (즉, 각 set에 있는 노드가 다른 set의 모든 노드와 이어지는 케이스는 인접한 것들에 대해 다른 정보를 가지면 된다. 색으로 치면 0번 노드가 red면 1,3번 노드는 blue 할당하는 것처럼!)

• Input
  graph 정보
• Output
  그래프의 bipartite 여부

예제

풀이

public class Solution {
    public bool IsBipartite(int[][] graph) {
        int n = graph.Length;
        int[] visited = new int[n];
        
        for (int i = 0; i < n; i++)
        {
            // 아직 정보 할당 안된 노드에 대해 DFS 진행 
            if (visited[i] == 0 && !DFS(graph, visited, i, 1)) return false;
        }

        return true;
    }
        
    private bool DFS(int[][] graph, int[] visited, int i, int setInfo)
    {
        visited[i] = setInfo; // set Info 할당 
        foreach (int node in graph[i])
        {
            if (visited[node] == -setInfo) continue; //인접 노드가 이미 다른 set이면 pass
            // 인접 노드가 같은 set이면 false return 
            if (visited[node] == setInfo || !DFS(graph, visited, node, -setInfo)) return false;
        }

        return true;
    }
    
}

결과

시간 의미 x