[LeetCode] Medium - 886 Possible Bipartition

▶886 - Possible Bipartition

▶문제

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.

 

▶예제

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

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

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

 

▶풀이

list를 graph로 먼저 바꾼 다음에 각 노드들로 bfs를 돌렸다.

두 개의 그룹으로 나눠져야 하기에, 1과 -1로 했다.

만약 a가 갈 수 있는 곳에 b가 있다면 color 값을 비교해 본다.

만약에 같다면 허용될 수 없는 예이기에, false를 반환해 준다.

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)

        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
        
        color = [0 for _ in range(n + 1)]

        for i in range(1, n + 1):
            if color[i] != 0:
                continue
            tmp = collections.deque()
            tmp.append(i)
            color[i] = 1

            while tmp:
                cur = tmp.popleft()
                for e in graph[cur]:
                    if color[e] != 0:
                        if color[cur] == color[e]:
                            return False
                    else:
                        color[e] = -color[cur]
                        tmp.append(e)

        return True