20240322_순위(프로그래머스)

오늘의 TIL은 순위라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

 

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았다.

권투는 1대1 방식으로 진행되고, 만약 A 선수가 B보다 실력이 좋다면 A 선수는 B 선수를 항상 이긴다.

심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 한다.

하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없다.

 

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때,

정확하게 순위를 매길 수 있는 선수의 수를 return 하시오.

 

 

제한 조건

선수의 수는 1명 이상 100명 이하이다.

경기 결과는 1개 이상 4,500개 이하이다.

results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미이다.

모든 경기 결과에는 모순이 없다.

 

 

해결 방안

그래프 이론과 플로이드-워셜 알고리즘을 적용하여 문제를 풀이.

각 선수를 그래프의 노드로 생각하고, 한 선수가 다른 선수를 이긴 결과를 방향이 있는 간선으로 표기.

이 그래프에서 모든 노드 쌍에 대하여 도달 가능성을 확인하여

정확한 순위를 결정할 수 있는 선수의 수를 구한다.

 

 

통과한 답안

using System;

public class Solution {
    public int solution(int n, int[,] results) {
        int answer = 0;
        
        bool[,] winGraph = new bool[n, n];

        for (int i = 0; i < results.GetLength(0); i++)
        {
            int win = results[i, 0] - 1;
            int lose = results[i, 1] - 1;
            winGraph[win, lose] = true;
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (winGraph[j, i] && winGraph[i, k])
                    {
                        winGraph[j, k] = true;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++)
        {
            int count = 0;
            for (int j = 0; j < n; j++)
            {
                if (winGraph[i, j] || winGraph[j, i])
                {
                    count++;
                }
            }

            if (count == n - 1)
            {
                answer++;
            }
        }
        return answer;
    }
}

 

 

선수들 간의 승패를 winGraph로 저장 

bool[,] winGraph = new bool[n, n];

for (int i = 0; i < results.GetLength(0); i++)
{
    int win = results[i, 0] - 1;
    int lose = results[i, 1] - 1;
    winGraph[win, lose] = true;
}

 

winGraph를 두 선수의 승패를 알 수 있게 두 값에 대하여 bool 값으로 저장한다.

이 때, 선수의 번호는 0번부터 시작하므로 result에서 1을 빼준다.

 

 

둘 이상의 선수가 연결된 경우에도 승패를 기록(플로이드-워셜 알고리즘)

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < n; k++)
        {
            if (winGraph[j, i] && winGraph[i, k])
            {
                winGraph[j, k] = true;
            }
        }
    }
}

 

A, B, C의 세 선수가 있을 때,

A가 B를 이기고 B가 C를 이겼으면 강한 순서가 A > B > C로 확인할 수 있으므로,

위의 if 식을 통해서 j가 i를 이겼고 i가 k를 이겼다면 j가 k를 이길 수 있다로 기록한다.

 

 

winGraph를 통해 순위를 확정할 수 있는 선수의 수 구하기

for (int i = 0; i < n; i++)
{
    int count = 0;
    for (int j = 0; j < n; j++)
    {
        if (winGraph[i, j] || winGraph[j, i])
        {
            count++;
        }
    }

    if (count == n - 1)
    {
        answer++;
    }
}

 

한 선수가 winGraph에서 다른 선수와의 승패를 알 수 있으면 count++하는데,

이 count가 n - 1(자기 자신을 빼므로)가 된다면 모든 선수와의 승패를 정할 수 있다는 것이다.

따라서 그 선수는 순위를 확정할 수 있는 선수가 된다.

모든 선수에 대해서 위의 과정을 반복하면서 순위를 확정할 수 있는 선수의 수(answer)를 센다.

 

 

오늘은 플로이드-워셜 알고리즘을 이용하여 최단경로문제와 비슷하게

승패를 정할 수 있는 경로가 있는지 확인하는 방식으로 위의 문제를 해결하였다.

플로이드-워셜 알고리즘은 for문을 3중으로 사용하므로 시간 복잡도가 O(n^3)이므로

n(선수의 수)이 최대 100인 이 경우에는 사용할 수 있었다.