[LeetCode] 886. Possible Bipartition [JAVA(자바)]

'기술면접 라이브코딩 - 승지니어'를 보고 작성한 글입니다. 😀

문제 👉 <Possible Bipartition - LeetCode>

1. 문제 ()

N명의 사람을 두 그룹으로 나눈다.

Dislikes[i] = [a,b] 일 때, a 와 b 는 서로 다른 그룹이어야 한다.

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

2. 풀이

이분그래프 와 DFS 를 이용한 풀이

• 이분그래프를 통해 N명의 사람을 2개의 그룹으로 나눈다.
• DFS 를 통해 dislikes한 사람을 모두 다른 그룹(true/false)으로 보낸다.
  • visited 를 통해 이미 그룹이 정해진 dislieks의 사람과 그룹을 확인한다.

3. 코드

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        List<List<Integer>> adjList = new ArrayList<>();
        boolean[] visited = new boolean[N];
        boolean[] color = new boolean[N];

        for (int i=0; i<N; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] d : dislikes) {
            int a = d[0] - 1;
            int b = d[1] - 1;
            adjList.get(a).add(b);
            adjList.get(b).add(a);
        }

        for (int i=0; i<N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (!isBipartiteDfs(i, adjList, visited, color))
                    return false;                
            }
        }

        return true;
    }

    boolean isBipartiteDfs(int cur, List<List<Integer>> adjList, boolean[] visited, boolean[] color) {
        for (int next : adjList.get(cur)) {
            if (!visited[next]) {
                visited[next] = true;
                color[next] = !color[cur];
                if (!isBipartiteDfs(next, adjList, visited, color))
                    return false;
            } else if (color[cur] == color[next]){
                return false;
            }
        }

        return true;
    }

}

• 결과 :

Time Submitted	Status	Runtime	Memory	Language
05/04/2021	Accepted	13 ms	46.7 MB	java

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋