LeetCode (C/C++, Java) 785. Is Graph Bipartite?

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

 

---

풀이

아직 방문하지 않은 노드에 대해 방문하여 bfs로 연결된 노드들을 모두 확인한다.

이 때 다음에 방문하는 노드들은 현재 노드와 다른 그룹으로 묶는다. 현재 그룹이 A라면 B로, B라면 A로 묶는다.

묶던 중 현재 노드와 다음 노드가 같은 그룹으로 묶인다면 이분 그래프가 아니므로 false를 반환한다.

---

C/C++ 코드

#define A 1
#define B 2

class Solution {
public:
    int group[101];
    bool bfs(vector<vector<int>>& graph, int now) {
        queue<int> q;
        q.push(now);
        group[now] = A;

        while (!q.empty()) {
            int now = q.front();
            q.pop();

            for (int next : graph[now]) {
                if (group[now] == group[next]) return false;
                if (group[next] > 0) continue;
                group[next] = group[now] == A ? B : A;
                q.push(next);
            }
        }
        return true;
    }
    bool isBipartite(vector<vector<int>>& graph) {
        for (int i = 0; i <= 100; i++) 
            group[i] = -1;
        
        for (int i = 0; i < graph.size(); i++) {
            if (group[i] > 0) continue;
            if (!bfs(graph, i)) return false;
        }
        return true;
    }
};

 

Java 코드

class Solution {
    private static int[] group;
    private static final int A = 1;
    private static final int B = 2;

    private static boolean find(int[][] graph, int start) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        group[start] = A;
        
        while (!q.isEmpty()) {
            int i = q.poll();
            int befGroup = group[i];
            int nowGroup = befGroup == A ? B : A;

            for (int j : graph[i]) {
                if (befGroup == group[j]) {
                    return false;
                }
                if (group[j] > 0) continue;
                group[j] = nowGroup;
                q.add(j);
            }
        }
        return true;
    }
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        group = new int[n];

        for (int i = 0; i < n; i++)
            group[i] = -1;

        for (int i = 0; i < graph.length; i++) {
            if (group[i] > 0) continue;
            if (!find(graph, i))
                return false;
        }
        return true;
    }
}