(C#)순위

코딩테스트 연습 - 순위 | 프로그래머스 스쿨

프로그래머스

 

아우... 정말 머리아픈 문제였다.

플로이드-워셜이라는 알고리즘을 사용해서 풀었다.

플로이드-워셜 알고리즘은 구현은 간단한데, 그 개념이 직관적으로 머릿속에 들어오지를 않는다. 아직까지도 잘 모르겠다.

 

문제는 두 단계로 풀었다.

1단계: 주어진 results를 가지고 인접행렬을 만든다

2단계: 만들어진 인접행렬을 가지고 플로이드-워셜 알고리즘을 적용한다

 

그리고 마지막으로 다른 모든 노드와 이어지는 노드를 센다.

 

플로이드-워셜 알고리즘은 원래 모든 노드간의 최단경로를 찾는 알고리즘이다.

그러나 이 문제에서는 최단경로를 알 필요는 없고, 경로가 이어져있는지만 찾으면 된다.

왜냐면, 어떤 선수의 순위를 정확히 안다는건 다른 모든 선수들에 대해서 승패를 가릴 수 있다는 뜻이기 때문이다.

두 선수의 승패 관계를 승자 -> 패자로 이어지는 단방향 그래프로 나타낼 수 있다.

예제의 경우

예제의 경우를 그래프로 그리면 위와 같을 것이다.

 

1번 선수를 살펴보면, 1-2, 1-5경로는 있지만 1-3, 1-4 경로는 없다. 1은 2를 이기고, 5를 이기지만, 3이나 4와는 어떻게 될지 알 수 없다(1->2, 1->5, 1..3, 1..4).

2번 선수를 살펴보면 1-2, 2-3, 2-4, 2-5의 경로가 모두 있다. 2는 5는 이기지만(2->5) 1, 3, 4에게 진다(1->2, 3->2, 4->2).

역방향도 괜찮다. 화살표가 역방향이라는건 패배한다는 뜻이다.

 

코드

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int n, int[,] results)
    {
        int answer = 0;
        bool[,] graph = new bool[n + 1, n + 1];
        for (var i = 0; i < results.GetLength(0); i++)
        {
            var x = results[i, 0];
            var y = results[i, 1];
            graph[x, y] = true;
        }

        for (var k = 1; k < n + 1; k++)
        {
            for (var i = 1; i < n + 1; i++)
            {
                for (var j = 1; j < n + 1; j++)
                {
                    if (graph[i, k] && graph[k, j])
                    {
                        graph[i, j] = true;
                    }
                }
            }
        }

        for (var i = 1; i < n + 1; i++)
        {
            var count = 0;
            for (var j = 1; j < n + 1; j++)
            {
                if (graph[i, j] || graph[j, i]) count++;
            }
            if (count == n - 1) answer++;
        }

        return answer;
    }
}

 

결과