프로그래머스 _ 순위

https://programmers.co.kr/learn/challenges?selected_part_id=14393

프로그래머스

 

1. 풀이방법

이 문제는 1번이 2번을 이겼고 2번이 3번을 이겼으면 1번이 3번을 이길수 있다는 것에 주의를 기울여라.

 

1번 -> 2번 -> 3번

 

보다보면 2번이 중간지점이고 이러한 중간지점을 기준으로 계산하면 된다는 실마리를 얻게된다.

 

중간지점을 기준으로 계산하는 알고리즘 -> 플로이드 와샬

 

이 알고리즘의 형태를 조금 변형하면 쉽게 풀수있다.

 

마지막으로 승자와 패자를 모두 알수있는 노드들만 출력해주면 정답이다.

 

---

 

2. 코드 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

//1, 0 ,-1 승, 패, 알수없음
int floyed[102][102];

void floyedInit(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            floyed[i][j] = -1;
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    //초기 세팅
    floyedInit(n);
    for (int i = 0; i < (int)results.size(); i++)
    {
        int winner = results[i][0];
        int loser = results[i][1];

        floyed[winner][loser] = 1;
        floyed[loser][winner] = 0;
    }

    //floyed ㄱㄱ
    for (int mid = 1; mid <= n; mid++)
    {
        for (int winner = 1; winner <= n; winner++)
        {
            if (winner == mid)
                continue;
            //winner가 mid를 이겼다면 당연히 mid가 이긴사람도
            //winner가 이겼다.
            if (floyed[winner][mid] == 1)
            {
                for (int loser = 1; loser <= n; loser++)
                {
                    if (winner == loser)
                        continue;
                    if (floyed[mid][loser] == 1)
                    {
                        floyed[winner][loser] = 1;
                        floyed[loser][winner] = 0;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
        {
            if (floyed[i][j] == -1)
                cnt++;
        }
        if (cnt == 1)
            answer++;
    }

    return answer;
}

 

---

 

3. 후기

이 문제는 나혼자만의 힘으로 푼건 아니고 여러 차례시도하다 잘모르겠어서 프로그래머스 질문목록에 있는 힌트를 보고 영감을 얻어 풀었다. 역시 인터넷 형님들은 대단하시다.