[코딩테스트 C++] 순위

오늘의 문제

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

순위

나의 풀이

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

using namespace std;

bool check[101] = {false, };
int dfs(int in, vector<vector<int>> p){
    int nodes = 0;
    for(int i=0;i<p[in].size();i++){
        if(check[p[in][i]] == false){
            check[p[in][i]] = true;
            nodes += dfs(p[in][i], p);
        }
    }
    return nodes+1;
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> c(n);
    vector<vector<int>> p(n);
    for(int i=0;i<results.size();i++){
        c[results[i][0]-1].push_back(results[i][1]-1);
        p[results[i][1]-1].push_back(results[i][0]-1);
    }
    for(int i=0;i<n;i++){
        int pn = dfs(i, p)-1;
        int cn = dfs(i, c)-1;
        for(int j=0;j<101;j++)
            check[j] = false;
        if(pn + cn == n-1)
            answer++;
    }
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <string.h>
#include <queue>
#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    bool arr[101][101];
    memset(arr, 0, sizeof(arr));
    for(int i = 0; i < results.size(); i++){
        int a = results[i][0];
        int b = results[i][1];
        arr[a][b] = true;
    }

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr[i][k] && arr[k][j]) arr[i][j] = true;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for(int j = 1; j <= n; j++)
            cnt += (arr[i][j] + arr[j][i]);
        if(cnt == n-1) answer++;
    }
    return answer;
}

배울 점

• 처음에 어떻게 풀어야할지 고민을 너무 오래했다. 그래프 문제라는것을 알아채고도 성공조건이 무엇일지 금방 알아채지 못했다.
• child개수와 parent개수를 알아내면 순위알아낼 수 있다는 것을 알고나서는, DFS를 사용하여 각각 위, 아래의 노드를 저장해둔 벡터를 서칭했다.
• 그래프 문제인것을 알고나서는 점수, 노드의 개수 등으로 조건을 빨리 알아채야한다.

• 플로이드와샬로 풀이가 가능하다 와. 이사람이 이렇게 푼 이유는 오..와ㅏ.. 감탄만 나오네. 이유는 플로이드와샬을 사용하면 바로든 거쳐오든 나한테 들어오는 노드의 개수와 내가 바로가든 거쳐가든 갈수 있는 노드의 개수를 모두 알수있기 때문. 플로이드 와샬만 돌리면 한번에 부모노드개수, 자식노드개수를 알 수 있다. 와..