Is Graph Bipartite?

문제 파악

이분 그래프인지 아닌지 판별하는 문제

이분 그래프란 모든 노드를 두 개의 그룹으로 나눌 수 있고 모든 간선은 두 그룹 사이에만 있을 때의 그래프

→ 서로 연결된 노드는 반드시 다른 그룹

그룹마다 색을 다르게 칠해 이분 그래프인지 아닌지를 쉽게 확인 가능

예를 들어 왼쪽 그룹을 빨강, 오른쪽 그룹을 파랑으로 칠한다고 가정했을 때 연결된 두 노드에 같은 색깔이 칠해진다면 이분 그래프가 아님!
오른쪽 그래프는 파랑 노드끼리 연결되어 있어 이분 그래프 x

풀이

BFS를 사용해 모든 노드를 방문하면서 색깔을 칠하며 이분 그래프인지 아닌지 확인할 예정

1. 모든 노드를 색칠하지 않은 상태로 초기화 (-1로)
2. 색이 칠해지지 않은 노드 모두 BFS 돌기
   1. 큐 생성
   2. 시작 노드를 색 0으로 칠하기
   3. 연결된 노드들은 1로 칠하기
   4. 만약 연결된 노드를 칠하려고 했는데 이미 색이 칠해져 있다? false 반환
   5. 계속 색을 0과 1을 번갈아가면서 칠하기

코드

class Solution {
    public boolean isBipartite(int[][] graph) {
        //모든 노드 -1로 색깔 초기화
        int[] color = new int[graph.length];
        Arrays.fill(color, -1);

        //BFS 시작
        for (int i=0; i<graph.length; i++) {
            //아직 방문 안했다면(색깔이 안칠해져 있다면)
            if (color[i] == -1) {
                Queue<Integer> queue = new LinkedList<>();
                //큐에 현재 방문 노드 넣어주기
                queue.add(i);
                //0으로 색칠
                color[i] = 0;
                //큐가 빌 때까지 반복
                while (!queue.isEmpty()) {
                    int current = queue.poll();

                    //연결 노드 탐색
                    for (int next : graph[current]) {
                        //연결 노드에 색깔이 칠해져 있지 않다면
                        if (color[next] == -1) {
                            //다른 색깔 칠해주고 큐에 넣기
                            color[next] = 1 - color[current];
                            queue.add(next);
                        }
                        //만약 이미 같은 색이 칠해져 있다면
                        else if (color[current] == color[next]) {
                            //false 반환
                            return false;
                        }
                    }
                }
            }
        }
        //잘 넘어왔다면 true
        return true;
    }
}