[프로그래머스/그래프] 순위

문제 주소

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

 

풀이

count를 그래프 입력하면서 갱신하는 것이 아니라 그래프를 다 입력한 후에 갱신하는 것이 핵심이었다.

dfs 할 때 (현재 노드의 count += 이전 노드의 count) 이런 식으로 생각했었는데 그냥 count를 +1씩 해주면 되는 거였다.

 

코드

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

void update_count(int index, vector<vector<int>>& graph, unordered_map<int, int>& count, vector<bool>& visited){
    visited[index] = true;
    
    for (auto e: graph[index]){
        if (!visited[e]){
            count[e]++;
            update_count(e, graph, count, visited);
        }
    }
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    vector<vector<int>> win(n+1, vector<int>()); // 선수A, A가 이긴 선수들
    vector<vector<int>> lose(n+1, vector<int>()); // 선수 A, A가 진 선수들
   
    for (auto r : results){
        win[r[0]].push_back(r[1]);
        lose[r[1]].push_back(r[0]);
    }
    
    unordered_map<int, int> win_count;
    unordered_map<int, int> lose_count;

    for (int i = 1; i <= n; i++) {
        vector<bool> visited_win(n + 1, false);
        vector<bool> visited_lose(n + 1, false);

        update_count(i, win, win_count, visited_win);
        update_count(i, lose, lose_count, visited_lose);
    }
    
    for (int i = 1; i <= n; i++){
        if (win_count[i] + lose_count[i] == n-1){
            answer++;
        }
    }
    
    return answer;
}