<Lv.3> 순위 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/49191

📕 문제 설명

권투 경기의 결과가 주어진다.

results [a,b] = a 선수가 b 선수를 이겼음을 의미

이때, 결과 배열을 기반으로 순위가 확실히 정해지는 선수의 수 반환하기

• Input
  선수의 수 n, 경기 결과 results
• Output
  정확히 순위 매길 수 있는 선수의 수

예제

풀이

선수 본인 기준 이긴 선수들과 진 선수들의 합이 n-1이면 본인의 순위를 결정할 수 있다. 여기서 이긴 선수들과 진 선수들은 graph로 타고가면서 계산한다. (본인에게 이긴 선수들과 그 선수들에게 이긴선수, 본인에게 진 선수들과 그 선수들에게 진 선수들의 합)

using System;
using System.Collections.Generic;

public class Solution {
    List<int>[] winnerGraph;
    List<int>[] loserGraph;
    public int solution(int n, int[,] results) {
        int answer = 0;
        winnerGraph = new List<int>[n+1]; // i번 선수에게 이긴 선수
        loserGraph = new List<int>[n+1]; // i번 선수에게 진 선수
        
        for (int i = 1; i < n+1; i++) 
        {
            winnerGraph[i] = new List<int>();
            loserGraph[i] = new List<int>();
        }
        
        for (int i = 0; i < results.GetLength(0); i++) // 그래프 초기화
        {
            int winner = results[i,0];
            int loser = results[i,1];
            winnerGraph[loser].Add(winner);
            loserGraph[winner].Add(loser);
        }
        
        for (int i = 1; i < n+1; i++)
        {
            bool[] visited = new bool[n+1];
            visited[i] = true;
            // 순위 결정할 수 있는 경우
            if (GetNumOfWinner(i, visited) + GetNumOfLoser(i, visited) == n-1)
            {
                answer += 1;
            }
        }

        return answer;
    }
    
    
    private int GetNumOfWinner(int currNode, bool[] visited)
    {
        int numOfWinner = 0;
        // i번 선수에게 이긴 선수들 + 그 선수들에게 이긴 선수들
        List<int> winners = winnerGraph[currNode];

        foreach(int winner in winners)
        {
            if (!visited[winner])
            {
                visited[winner] = true;
                numOfWinner += 1;
                numOfWinner += GetNumOfWinner(winner, visited);   
            }
        }

        return numOfWinner;
    }

    private int GetNumOfLoser(int currNode, bool[] visited)
    {
        int numOfLoser = 0;
        // i번 선수에게 진 선수들 + 그 선수들에게 진 선수들
        List<int> losers = loserGraph[currNode];

        foreach(int loser in losers)
        {
            if (!visited[loser])
            {
                visited[loser] = true;
                numOfLoser += 1;
                numOfLoser += GetNumOfLoser(loser, visited);   
            }
        }

        return numOfLoser;
    }
}

결과