순위

💪순위 (프로그래머스)

사용언어: C++
BFS로 해결하였음
핵심: 인접리스트를 오름차순, 내림차순으로 만든뒤 큐를 각각 진행

---

1. 정답풀이(BFS)

#include <iostream>
#include <string>
#include <vector>
#include <deque>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    vector<int> graph[101];
    vector<int> rgraph[101];
    
    int answer = 0;
    
    for(int i=0; i<results.size(); i++){
        int x = results[i][0];
        int y = results[i][1];
        graph[x].push_back(y);  
        rgraph[y].push_back(x);  // 역순
    }
    
    for(int v=1; v<=n; v++){
        
        int check[101] = {0, };
        
        deque<int> q;
        
        int winner = 0;
        int loser = 0;
        
        q.push_back(v);
        check[v] = 1;
        
        while(!q.empty()){
            
            int now = q.front();
            q.pop_front();
                 
            for(int next : graph[now]){
                if(check[next] != 1){
                    q.push_back(next);
                    check[next] = 1;
                    winner++;
                }
            }
        }   
     
        q.push_back(v);
        
        while(!q.empty()){
            int now = q.front();
            q.pop_front();

            for(int next : rgraph[now]){
                if(check[next] != 1){
                    q.push_back(next);
                    check[next] = 1;
                    loser++;
                }
            }
        }
        
        if((winner + loser) == n-1){
            answer++;
        }
        
    }
    
    return answer;
}

---

2. 링크

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

코드업의 키순서와 유사한 문제
https://codeup.kr/problem.php?id=4714