프로그래머스 : 순위

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

코딩테스트 연습 - 순위

 

​

주어진 예제 : [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

이것을 승과 패에 관한 그래프를 별도로 만들어주면 아래 그림과 같습니다.

각 노드(선수)에서 최종 승리한 선수로 지나치는 모든 노드의 개수(승이 정해진 선수) + 각 노드(선수)에서 최종 패배한 선수로 지나치는 모든 노드의 개수(패가 정해진 선수) == n개라고 한다면, 그 노드(선수)의 순위를 정할 수 있을 것입니다.

이를 DFS를 이용하여 구현하였습니다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int dfs(vector<vector<int>>& graph, int node, vector<bool>& visit) {
    int cnt = 1;
    visit[node] = true;
    for(int i=0; i<graph[node].size(); i++) {
        if(!visit[graph[node][i]]) {
            cnt += dfs(graph, graph[node][i], visit);
        }
    }
    return cnt;
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> graph1(n+1), graph2(n+1);
    vector<bool> visit1, visit2;
    for(int i=0; i<results.size(); i++) {
        graph1[results[i][0]].push_back(results[i][1]);
        graph2[results[i][1]].push_back(results[i][0]);
    }
    for(int i=1; i<=n; i++) {
        visit1.clear(); visit2.clear();
        visit1.resize(n+1, false);
        visit2.resize(n+1, false);
        if(dfs(graph1, i, visit1) + dfs(graph2, i, visit2) == n + 1)
            answer++;
    }
    return answer;
}