[LeetCode] 886. Possible Bipartition

886. Possible Bipartition

Medium

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

 

Example 1:

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

Example 2:

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

Example 3:

Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

 

Constraints:

• 1 <= n <= 2000
• 0 <= dislikes.length <= 104
• dislikes[i].length == 2
• 1 <= dislikes[i][j] <= n
• ai < bi
• All the pairs of dislikes are unique.

---

문제 풀이

• 사람이 N개 있으며, 각각 사람들이 싫어하는 짝의 번호 두개로 이루어진 2차원 배열이 주어진다.
• 싫어하는 사람들끼리는 그룹으로 묶을 수 없다. 
• 사람들을 두 그룹으로 나눌 수 있는지를 구해야한다. 
• 모든 사람들이 두 그룹으로 나뉘었을때 그 그룹에는 싫어하는 사람이 생기면 안된다. 
• 제한 사항은 N^4 이기 때문에 완전탐색으로 문제를 접근할 수 있으며, 간선으로써 dislike 배열을 사용하여 그룹을 만들기 때문에 유니온 파인드로 접근할 수 있다. 

DFS

• 그룹에 싫어하는 사람이 없어야한다.
• 싫어하는 사람들을 나타내는 dislikes 배열은 간선을 나타내고 있기 때문에 현재 사람(노드)에서 싫어하는 사람을 연결했을때 그 사람들은 모두 현재 사람을 싫어한다. 
• 현재 사람에서 싫어하는 사람 다음으로 연결된 노드가 있고 이 노드가 현재 사람과 연결되지 않다면, 그 노드는 앞서 언급한 현재 사람을 싫어하지 않음을 의미한다. 
• 즉 연결될 간선들을 한번 연결해주고 0과 1을 사용하여 구분할 수 있다. 
• 싫어하는 사람들을 저장한 dislikes를 모두 양방향 간선들로써 인접행렬을 생성한다. 
• 그리고 col 배열을 생성하여 각 노드를 구분할 배열을 만들고 -1로 초기화한다. 
• 초기화를 통해 노드를 탐색한 것에 대한 중복을 방지할 수 있다. 
• 1부터 n까지 탐색하면서 만약 탐색 했던 노드가 아니면 현재 노드 번호와 구분할 매개변수를 넘겨 dfs 재귀함수를 호출한다.
• 첫 시작노드는 0의 구분 값을 col에 넣게 되고, 현재 노드에 연결된 노드들을 탐색한다.
• 탐색시 현재 노드와 다음으로 이동할 노드의 구분 값이 같다면 False를 리턴한다. 
• 만일 구분 값이 설정되지 않은 새 노드라면 dfs를 호출하는데, 이때 1 - 구분 값 매개변수를 넣는다. 
• 1 - 구분 값 매개변수는 다음 재귀호출시 0에서 1로 1에서 0으로 바뀌게 해준다.
• 만일 호출 후 리턴값이 false 라면 false를 리턴한다. 
• 이는 한번이라도 false가 리턴되면 재귀호출을 마지막까지 리턴시키기 위함이다. 
• 다시 본 코드로 돌아와서, 리턴값이 false면 노드들 끼리, 즉 현재 노드와 다음 노드의 구분 값이 같다면 false를 리턴한다. 

Union Find

• 싫어하는 사람들을 그룹으로 묶는 것이 아니라, 현재 노드에서 싫어하는 사람들로 연결된 노드들을 그룹으로 묶는다. 
• 현재 노드를 싫어하는 노드들을 그룹으로 묶는 것은 한 노드를 싫어하는 노드들은 각자 싫어하지 않을 거라는 가정에서 시작한다. 
• 매번 위 행동을 반복하면서 이전에 형성된 한 노드를 싫어하는 그룹을 참고로 답을 가려내기 시작한다.
• 즉, 그 그룹은 자신들끼리 싫어하지 않는 그룹인데 다음 노드 회차에서 싫어하는 노드들을 find로 그룹이 되어있는지 확인하면 싫어하는 사람들끼리 묶였는지 알 수 있다. 
• 두 그룹으로 나눌때 사람의 수는 상관 없기 때문에 싫어하는 사람들이 이전 그룹에서 중복되어 겹치지만 않으면 두 그룹으로 쪼갤 수 있음을 의미한다. 
• 만약 중복되어 있다면 2개로 쪼개지는 것이 아니라 그 이상으로 쪼개질 수 있기 때문에 False를 리턴한다. 
• find는 재귀함수로 부모 배열에 각각 연결된 노드들을 저장한다. 
• 최상위 부모 노드번호를 저장하기 위해 find 함수가 리턴한 값을 현재 노드의 부모 배열에 저장한다. 
• union 함수는 두 노드 번호의 부모를 구하고 rank에 맞게 최상위 부모를 저장시킨다. 
• rank를 사용하는 이유는 단지 순서에 대한 처리시간을 빠르게 하기 위해서이다. 
• 중복되는 노드들이 생기면 자연스럽게 랭크를 증가시키고 증가시킨 노드는 자식 노드의 층을 의미한다고 볼 수 있다. 
• 층에 맞게 부모 노드를 할당해주면 find로 노드를 탐색할때 O(1)의 속도로 최상 부모 노드를 찾을 수 있다. 
• 양방향 인접 2차원 배열을 만들고 각각 싫어하는 노드들의 번호들을 저장한다. 
• 사람의 번호들을 탐색하면서 그 사람의 번호를 싫어하는 사람들의 번호를 탐색한다. 
• 만일 현재 노드와 현재 노드를 싫어하는 사람의 노드의 최상위 부모가 같다면 False 를 리턴한다. 
• 이미 만들어진 그룹에서 부모의 중복이 발생하면 그룹은 2개 초과가 된다. 
• 그 후, 현재 노드의 싫어하는 노드들의 첫 노드와 모든 현재 노드를 싫어하는 노드를 그룹으로 만들기 위해 Union 함수를 호출한다.

소스 코드

DFS

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        def dfs(node, n_col):
            col[node] = n_col
            for neighbor in adj[node]:
                if col[neighbor] == col[node]:
                    return False
                if col[neighbor] == -1:
                    if not dfs(neighbor, 1 - n_col):
                        return False
            return True
        adj = [[] for _ in range(n + 1)]
        for dislike in dislikes:
            adj[dislike[0]].append(dislike[1])
            adj[dislike[1]].append(dislike[0])
        col = [-1] * (n + 1)
        for i in range(1, n + 1):
            if col[i] == -1:
                if not dfs(i, 0):
                    return False
        return True

Union find

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        s = n + 1
        p = [i for i in range(s)]
        r = [0] * s

        def find(num):
            if p[num] != num:
                p[num] = find(p[num])
            return p[num]
        
        def union(a, b):
            ap = find(a)
            bp = find(b)

            if ap == bp: return
            if r[ap] < r[bp]:
                p[ap] = bp
            elif r[ap] > r[bp]:
                p[bp] = ap
            else:
                p[bp] = ap
                r[ap] += 1
        adj = [[] for _ in range(n + 1)]
        for lst in dislikes:
            adj[lst[0]].append(lst[1])
            adj[lst[1]].append(lst[0])
        
        for i in range(1, n + 1):
            for j in adj[i]:
                if find(i) == find(j):
                    return False
                union(adj[i][0], j)
        return True