<Medium> Flower Planting With No Adjacent (LeetCode : C#)

https://leetcode.com/problems/flower-planting-with-no-adjacent/

📕 문제 설명

1~n으로 라벨링된 n개의 정원이 있다. x_i번 정원과 y_i번 정원의 양방향 path를 나타내는 path 배열이 주어진다.
paths[i] = [x_i, y_i]

모든 정원은 최대 3가지 path가 존재한다. 각 정원에 심을 꽃 종류를 결정해야 하는데 연결된 정원은 다른 종류의 꽃을 심어야 한다. 이 조건을 만족하는 answer 반환하기

answer[i] = (i+1)번째 정원에 심긴 꽃 종류
(flower type은 1,2,3,4가 존재한다.)

• Input
  정원 개수 n, 인접 정원 정보 paths
• Output
  심을 꽃 종류 정보

예제

풀이

인접 리스트 만들고 인접한것들 color확인하면서 사용하지 않은 색 할당하기

public class Solution {
    public int[] GardenNoAdj(int n, int[][] paths) {  
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) answer[i] = 1;

        List<int>[] adjList = new List<int>[n+1];

        for (int i = 1; i < n + 1; i++)
        {
            adjList[i] = new List<int>();
        }

        for (int i = 0; i < paths.Length; i++)
        {
            adjList[paths[i][0]].Add(paths[i][1]);
            adjList[paths[i][1]].Add(paths[i][0]);
        }

        for (int i = 1; i < n + 1; i++)
        {
            HashSet<int> neighborColors = new HashSet<int>();
            foreach(int neighbor in adjList[i])
            {
                neighborColors.Add(answer[neighbor - 1]);
            }

            for (int colorIndex = 1; colorIndex <= 4; colorIndex++)
            {
                if (!neighborColors.Contains(colorIndex))
                {
                    answer[i - 1] = colorIndex;
                }
            }
        }

        return answer;
    }
}

결과