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

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

프로그래머스

그래프 Graph

경기결과(a승 b패)가 주어지면, 정확한 순위를 알 수 있는 선수의 수를 반환하는 문제

 

접근방법

첨에 진짜 막막했는데, 선수들의 경기를 간선으로 그래프를 이어보면 본인의 부모노드갯수(본인보다 점수가 높은) + 자식노드갯수(본인보다 점수가 낮은) 값이 총 선수의 수 n - 1(본인) 과 같으면 본인의 순위가 분명한 경우인 것을 고려해서 풀 수 있는 문제다.

 

인접행렬 두개를 만들어서, 하나는 각 노드의 부모노드를 저장하는 2차원 배열, 다른 하나는 각 노드의 자식노드를 저장하는 2차원 배열을 만들어서 사용했다.

bfs처럼 큐를 사용했고, 본인의 모든 부모노드(부모노드의 부모노드 모두 포함)와, 본인의 모든 자식노드(이것도)를 집합에 담고, 그 집합의 사이즈가 n (본인도 포함함) 이면 순위를 매길 수 있는 노드로 판단하는 로직으로 구했음

 

오답노트

원래는 set만 쓰고 visit는 안썼다가, 시간초과나서 visit로 방문여부도 체크해가면서 했다.

이미 방문했으면, 다시 큐에 넣지 않음

그리고 마지막에 집합 사이즈 체크할 때 n-1넣었다가 틀렸었음

 

소스코드

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

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    vector<vector<int>> parents(n+1);
    vector<vector<int>> children(n+1);
    
    for(int i = 0 ; i < results.size() ; i++){
        int p = results[i][0];
        int c = results[i][1];
        parents[c].push_back(p);
        children[p].push_back(c);
    }
    
    for(int i = 1 ; i <= n ; i++){
        // 각 선수당 나보다 '확실히' 점수 높은 사람 수, 낮은 사람 수 세기
        set<int> s;
        queue<int> q;
        q.push(i);
        vector<bool> visit(n+1, false);
    
        // 점수 높은 사람 부터
        while(!q.empty()){
            int now = q.front();
            q.pop();
            s.insert(now);
            visit[now] = true;

            for(int j = 0 ; j < parents[now].size() ; j++){
                if(!visit[parents[now][j]])
                    q.push(parents[now][j]);
            }
        }
        
        // 점수 낮은 사람
        q.push(i);
        while(!q.empty()){
            int now = q.front();
            q.pop();
            s.insert(now);
            visit[now] = true;
            
            for(int j = 0 ; j < children[now].size() ; j++){
                if(!visit[children[now][j]])
                    q.push(children[now][j]);
            }
        }
        
        if(s.size() == n){
            answer++;   
        }
    }
    
    return answer;
}