<Medium> Possible Bipartition (LeetCode : C#)

https://leetcode.com/problems/possible-bipartition/

📕 문제 설명

n명의 사람들을 두 개의 그룹으로 나눌려고 한다. 싫어하는 사람을 나타내는 정보가 주어지고 이들은 서로 같은 그룹에 있으면 안된다. 모든 사람들을 두 개의 그룹으로 나눌 수 있는지에 대한 여부 반환

• Input
  사람 수 (int), 싫어하는 사람 정보 (int[][])
• Output
  모든 사람들을 두 개의 그룹으로 나눌 수 있는지에 대한 여부

예제

풀이

인접 리스트 만들어놓고 group number 다르게 할당할 때 partition이 이루어지는지 재귀로 확인하는 식으로 구현

public class Solution {
    List<int>[] adj;
    public bool PossibleBipartition(int n, int[][] dislikes) {
        adj = new List<int>[n + 1];
        for (int i = 1; i <= n; i++) 
        {
            adj[i] = new List<int>();
        }
        
        foreach (int[] dislike in dislikes) 
        {
            adj[dislike[0]].Add(dislike[1]);
            adj[dislike[1]].Add(dislike[0]);
        }
        
        int[] location = new int[n + 1]; // 1, 0, -1 
        for (int i = 1; i <= n; i++) 
        {
            if (!Partition(i, location[i], location)) return false;
        }
        
        return true;
    }
    
    private bool Partition(int i, int groupNum, int[] location) 
    {
        if (groupNum == 0) groupNum = 1; // 처음 들어오는 경우 1로 초기화
        if (location[i] == groupNum) return true; 
        if (location[i] == -groupNum) return false;
        location[i] = groupNum; // 위치 할당
        foreach (int j in adj[i]) 
        {
            if (!Partition(j, -groupNum, location)) return false; // 인접한 것 반대 group number 할당해주고 partition 되는지 확인
        }
        return true;
    }
}

결과