LeetCode 886

문제 링크

잡담.

일은 진도가 안나가고(나때문이 아니다.. 소스를 봐야하는데 그걸 못하고 있는 중이다.), 답답해서 오랜만에 쓰는 LeetCode 풀이.

문제 설명 및 풀이.

문제 설명.

자연수 n과 1~n 이하의 서로 다른 두 수를 가지는 배열들의 배열인 dislike가 주어진다. 문제의 설명에서는 1부터 n까지의 사람이 있고, dislike 안쪽의 배열에 있는 서로 다른 두 숫자의 사람은 모두 사이가 나쁘다고 한다.(즉, 이외에는 사이가 좋다는 말이다.)
1부터 n까지의 사람들은 2개의 그룹으로 나눌 수 있는지 판별해보자.

문제 풀이.

문제를 처음 읽자마자 생각난 것은 1 ~ n 까지의 숫자를 정점으로 가지고, dislike를 edge로 가지는 그래프가 bipartite graph인지 아닌지를 판별하면 되겠다는 생각이 들었다. 그리고 잠시 고민끝에 길이가 n+1인 배열 하나를 만든 후, 정점 하나를 기준점으로 잡아주고, dislike에 따라 열심히 뺑뺑이를 돌리는 코드(이웃이면 기존의 숫자에 1을 더하는)를 만들었다.
이 과정에서 그래프가 disconnected 일 수 있다는 점을 고려해서 tmp를 추가했다.-설명에서 빠진 것 중에 dislike는 sort되어있다는 사실로 인해 잘 작동할 수 있었던 코드이다.

풀이 코드.

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        
        bigp = [-1 for _ in range(n+1)]
        bigp[dislikes[0][0]] = 0
        dislikes = deque(dislikes)
        tmp = deque()
        while True:
            while dislikes:
                x,y = dislikes.popleft()
                
                if bigp[x] != -1 and bigp[y] != -1:
                    if bigp[x]%2 == bigp[y]%2:
                        return False
                elif bigp[x] != -1:
                    bigp[y] = bigp[x] + 1
                elif bigp[y] != -1:
                    bigp[x] = bigp[y] + 1
                else:
                    tmp.append((x,y))
                    
            if not tmp:
                print(bigp)
                return True
            if bigp[tmp[0][0]] == -1:
                bigp[tmp[0][0]] = 0
            dislikes = tmp
            tmp = deque()