<Medium> Loud and Rich (LeetCode : C#)

https://leetcode.com/problems/loud-and-rich/

📕 문제 설명

n명의 사람이 주어질 때 다음을 만족하는 answer 반환하기

answer[x] = y, x보다 돈이 더 많거나 같은 사람 중 가장 quiet[y]가 적은 사람

richer[i] = [a_i, b_i], a_i가 b_i보다 돈이 더 많음
quiet[i] = i번째 사람의 quietness

• Input
  richer 정보, quiet 정보
• Output
  answer 배열

예제

풀이

public class Solution {
    public int[] LoudAndRich(int[][] richer, int[] quiet) {
        int[] answer = new int[quiet.Length];
        List<List<int>> richerAdjList = new List<List<int>>();
        bool[] visited = new bool[quiet.Length];

        // 인접 리스트 초기화
        for (int i = 0; i < quiet.Length; i++) richerAdjList.Add(new List<int>());
        for (int i = 0; i < richer.Length; i++) // key = 특정 사람, value = 특정 사람보다 더 부자인 사람들 
        {
            int poor = richer[i][1];
            int rich = richer[i][0];
            richerAdjList[poor].Add(rich);
        }

        for (int i = 0; i < quiet.Length; i++)
        {
            if (visited[i] != true)
            {
                // i번째 사람에 대해 조건 만족하는 사람 찾아서 넣어주기 
                answer[i] = DFS(richerAdjList, quiet, visited, i, answer);
            }
        }

        return answer;
    }

    private int DFS(List<List<int>> adjList, int[] quiet, bool[] visited, int person, int[] answer){
        if (visited[person] == true) return answer[person];

        visited[person] = true;
        int quieterperson = person;
        foreach (int morericher in adjList[person])
        {
            // 본인보다 부자들 기준 DFS 돌려서 더 부자인 사람들에 대해 quiet person 받아오기 
            int richernlouder = DFS(adjList, quiet, visited, morericher, answer);
            answer[morericher] = richernlouder;
            // quiet person 갱신
            if (quiet[richernlouder] < quiet[quieterperson]) quieterperson = richernlouder;
        }
        return quieterperson;
    } 
}

결과