[프로그래머스LV3] 순위 (C++)

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

프로그래머스

 

위상정렬을 가장 먼저 떠올릴 수 있었지만 2번의 그래프 탐색으로도 끝낼 수 있는 문제이다.

 

승자 -> 패자 

패자 -> 승자 

 

그래프로 두개 만들어 두고 한번씩 탐색한 후 각 노드가 연관된 노드의 개수가 5이면 순위를 정할 수 있다고 판단한다.

 

이렇게도 풀 수 있지만 위상정렬을 사용해서도 풀 수 있는데 위상정렬은 그래프의 순서를 유지하여 정렬하는 방법이다.

 

 

문제에서 준 예제를 그래프로 표현하면 다음과 같고, lossSet. 즉 내가 진 노드를 만들어준다. 그리고 위상정렬의 개념처럼 Inorder가 0인 것 부터 탐색을 시작한다.

 

1, 4가 먼저 탐색을 시작하고 3의 inorder가 0이 되어 탐색한다. 그리고 2가 탐색을 시작한다.

 

2는 5를 만나게 되는데 이 때 2는 5에게 자신을 이긴 사람들을 모두 넘겨주어야한다. 그래서 모든 위상정렬 로직에 

 

LossSet[next] . insert ( int : LossSet[now] )

 

로직을 포함해야한다. 이렇게하면 최종적으로 5를 이긴 lossSet[5] 에는 1,2,3,4 가 들어가게 된다. 

 

하지만 여기서 끝나면 안되고 자신이 이긴 것도 포함해야한다. 그래서 winSet을 갱신한다.

 

winset은 만약 N번 노드가 lossSet[M]에 포함된다면. 2번 노드가 lossSet[5] 에 들어가 있다면 2는 5를 이겼다는 의미이므로 WinSet[2].insert(5) 로직이 들어가게된다.

 

최종적으로 이러한 로직까지 마무리 하고 나면

 

	WinSet	LossSet
1	2,5
2	5	1,3,4
3	2,5	4
4	2,3,5
5		1,2,3,4

 

이렇게 만들어지고 WinSet + LossSet 의 합이 n - 1과 같으면 정답으로 처리하여 개수를 새면 된다.

 

코드는 bfs두번한 코드이고 위상정렬은 개념만 새워보았다. 아마 구현도 그렇게 어렵지 않을 것이다. 

 

#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <iostream>

using namespace std;

vector<int> node[101];
vector<int> node2[101];

int bfs(int now, bool flag){
    bool visited[101];
    memset(visited, false, sizeof visited);
    
    queue<pair<int, int>> q;
    visited[now] = true;
    
    q.push({now, 0});
    int res = 0;
    while(!q.empty()){
        int nowNode = q.front().first;
        int cnts = q.front().second;
        q.pop();
            
        vector<int> tmp;
        if(flag) tmp = node[nowNode];
        else tmp = node2[nowNode];
        
        for(int next : tmp){
            if(visited[next]) continue;
            visited[next] = true;
            res++;
            q.push({next, cnts + 1});
        }
    }
    
    return res;
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(int i = 0; i < results.size(); i++){
        node[results[i][0]].push_back(results[i][1]);
        node2[results[i][1]].push_back(results[i][0]);
    }
    
    for(int i = 1; i <= n; i++){
        int a = bfs(i, true);
        int b = bfs(i, false);
        if(a + b + 1 == n) answer++;
    }
    
    return answer;
}