[LeetCode] 785. Is Graph Bipartite? (java)

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

 

 

문제 파악

n개의 노드를 가진 무방향 그래프가 주어진다. 각 노드는 0부터 n-1까지 번호가 매겨져 있으며, graph[u]는 노드 u와 인접한 노드들의 배열을 의미한다.

주어진 그래프가 이분 그래프(bartite)인지 여부를 return하라.

 

 

문제 풀이

그래프를 순회하면서 노드를 두 개의 그룹으로 나눌 수 있는지 확인해야 한다.

• DFS
• 또는 BFS

를 사용하여 탐색하면서 그룹을 구분하면 된다.

BFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        boolean[] set = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Queue<Integer> queue = new LinkedList<>();
                visited[i] = true;  // set A 설정
                queue.add(i);

                while (!queue.isEmpty()) {
                    int curr = queue.remove();

                    for (int next : graph[curr]) {
                        if (!visited[next]) {  // 아직 방문하지 않은 node이면
                            set[next] = !set[curr];
                            visited[next] = true;
                            queue.add(next);
                        }
                        else {  // 이미 방문한 node이면
                            if (set[curr] == set[next]) return false;
                        }
                    }
                }
            }
        }

        return true;
    }
}

 

📊 실행 결과

 

DFS

class Solution {
    static boolean[] visited;
    static boolean[] set;
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        visited = new boolean[n];
        set = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (!dfs(i, graph)) return false;
            }
        }

        return true;
    }

    boolean dfs(int curr, int[][] graph) {
        visited[curr] = true;

        for (int next : graph[curr]) {
            if (!visited[next]) {
                set[next] = !set[curr];
                visited[next] = true;
                boolean result = dfs(next, graph);
                if (!result) return false;
            }
            else {
                if (set[curr] == set[next]) return false;
            }
        }

        return true;
    }
}

 

📊 실행 결과