[LeetCode] Is Graph Bipartite?

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

 

 

문제 파악

-0~n까지의 노드가 주어지고 각 노드의 간선 status가 주어짐

-이분 그래프 true or false 찾아라

• 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.

접근 방법

-이분 그래프 :

• 두 개의 독립된 집합으로 정점을 나눌 수 있다.
• 모든 간선이 한 집합의 정점과 다른 집합의 정점을 연결해야 한다.

-"독립적"이라는 말은 같은 그룹의 정점들끼리는 직접 연결된 간선이 없다는 뜻

⇒ 그래프를 돌며 노드 하나씩 순회 → 순회하면서 해당 노드의 그룹(color) 조회 → 연결

⇒ 색칠하는 도중 인접한 정점이 같은 색으로 색칠되어야만 하는 상황이 발생하면 이분 그래프가 아니라고 판단

 

코드 구현

import java.util.*;
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        for(int i=0;i<n;i++){//여기로 돌아오려면 color가 1 혹은 -1이면서 자식과 색이 달라 통과한 경우
            if(color[i]==0){//방문했는데도 또 돌 수도 있으니 부모노드도 0인지 아닌지 검증해줘야 함
                Queue<Integer> que = new ArrayDeque<>();
                que.add(i);
                color[i] = 1;
                while(!que.isEmpty()){
                    int node = que.poll();
                    for(int k:graph[node]){
                        if(color[k]==0){//방문 아직 안한 자식이라면
                            color[k] = -color[node];//자식(연결된 노드)가 다른 그룹이 되게 함. 1이면 -1 배척해버리기
                            que.add(k);
                        }else if(color[k]==color[node]){//자식 정점이 이미 그룹이 있고, 부모와 같은 집합에 속한거라면
                            return false;// 이분 그래프가 아님. 바로 리턴
                        }
                    }
                }
            }
        }
        return true;// 모든 정점이 두 집합으로 나눌 수 있음
    }
}

배우게 된 점

뭔가 땅따먹기하는 것처럼.. 색을 하나씩 칠해가며 그룹 선점을 해가는 방식처럼 느껴졌다.

어떠한 기준을 먼저 정하고(기준:부모와 자식은 같은 그룹일 수 없다.) → 그에 따라 선점해가며

만일 돌다가 자식=부모라면 주저없이 리턴.

dfs나 bfs를 풀면서 이런 경우의 문제는 처음 봐서 당황스러웠지만

역시나 방문을 했는지 안했는지 체크하는 로직 visited 개념과, 그 인접 노드를 구하기 위한 큐 자료구조까지

전체적인 틀은 비슷했다.