[LeetCode] 785. Is Graph Bipartite?

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

Is Graph Bipartite? - LeetCode

각 노드의 번호가 0에서 n-1 사이인 노드가 n개인 방향성 없는 그래프가 있습니다. 2D 배열 그래프가 주어지는데, 그래프[u]는 노드 u가 인접한 노드들의 배열입니다. 그래프는 다음과 같은 속성을 가집니다:
- 그래프[u]에 u가 포함되지 않음
- 그래프[u]에 중복 값이 포함되지 않습니다.

- v가 그래프[u]에 있으면, u는 그래프[v]에 있습니다. (그래프가 방향이 없음).
- 그래프가 연결되지 않을 수도 있습니다. 즉, 두 노드 u와 v 사이에 경로가 없는 두 노드가 있을 수 있습니다.
그래프의 모든 가장자리가 집합 A의 노드와 집합 B의 노드를 연결하도록 노드를 두 개의 독립된 집합 A와 B로 분할할 수 있으면 그래프는 이분형입니다.

그래프가 이분형일 경우에만 참을 반환합니다.

---

접근 방법

1. 이분 그래프란?

이분 그래프는 모든 노드를 두 가지 색상만으로 칠할 수 있는 그래프입니다. 따라서 각 간선이 연결하는 두 정점의 색이 서로 다르게 색칠되어야 합니다.

2. 어떤 알고리즘을 사용할까? 모든 노드를 방문해야 하므로 완전탐색을 사용합니다.

DFS, BFS 둘 다 가능하나 저는 BFS를 선택했습니다.

3. 시간복잡도

graph.length == n이므로 완전탐색을 해도 괜찮을 것 같다는 판단을 했습니다.

4. 코드 설계

• 주어진 int[][] graph로 인접리스트를 생성합니다. 이때 주의할 점은 양방향이므로 a → b, b → a 모두 연결해야 합니다.
• 노드 별로 색상을 구분 지을 수 있는 int[] colors선언합니다.
  • 방문하지 않았을 시 초기값 = 0
  • 방문 시, 1 또는 -1
  • 다음 방문 시, -1 또는 1
• 아직 색칠되지 않은 정점을 BFS탐색합니다.
  • 노드의 인접 노드까지 순회합니다.
  • BFS는 큐를 이용하므로 큐를 선언합니다. (예약을 걸어두는 용도)
  • 큐에서 poll() 한 후 아직 색칠되어있지 않으면, 그전 정점의 색과 다른 색을 넣습니다.
  • 만약 이미 색칠된 정점이라면, 그 전 정점의 색과 합이 0이 아니라면 false를 반환합니다.

코드 구현

import java.util.*;
class Solution {
    public boolean isBipartite(int[][] graph) { 
        Map<Integer, List<Integer>> bfsTree = new HashMap<>();
        
        for (int i = 0; i < graph.length; i++) {
            for (int edge : graph[i]) {
                bfsTree.putIfAbsent(i, new ArrayList<>());
                bfsTree.get(i).add(edge);
                bfsTree.putIfAbsent(edge, new ArrayList<>());
                bfsTree.get(edge).add(i);
            }
        }
        
        int[] colors = new int[graph.length];

        for (int i = 0; i < graph.length; i++) {
            if (colors[i] == 0) {
                List<Integer> list = bfsTree.get(i);
                if (list != null && !list.isEmpty()) {
                    if (!bfs(i, colors, bfsTree)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
    
    public boolean bfs(int startVertex, int[] colors, Map<Integer,List<Integer>> bfsTree) {
        Deque<Integer> queue = new ArrayDeque<>();

        queue.add(startVertex);
        colors[startVertex] = 1;

        while (!queue.isEmpty()) {
            int targetVertex = queue.poll();

            List<Integer> neighbors = bfsTree.get(targetVertex);
            if (neighbors == null) {
                continue;
            }

            for (int nextVertex : neighbors) {
                if (colors[nextVertex] == 0) {
                    queue.add(nextVertex);
                    colors[nextVertex] = -1 * colors[targetVertex];
                } else if (colors[nextVertex] + colors[targetVertex] != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

 

해당 문제의 경우 이분 그래프의 정의를 이해하는 게 가장 어려웠습니다.