정올 #2462 백준 #2458 키 순서

백준 #2458
정올 #2462

그래프 DFS, 벡터 이용

처음에는 [등수를 알고싶은 학생][비교하는 학생(n명)] 이렇게 이차원 배열을 사용해야 한다고 생각했는데, 그냥 main에서 for문으로 n번 dfs를 돌리면 되는 일이었다.

#include <stdio.h>
#include <vector>
using namespace std;
 
int n, m, a, b;
vector<int> smaller[501]; //i보다 작은 사람들
vector<int> taller[501]; //i보다 큰 사람들
int chk_small[501], chk_tall[501]; int cnt;
 
void small(int now){
    if(chk_small[now]) return; //방문했으면 return
    chk_small[now] = 1; //방문처리
    cnt++; //(cnt = 현재 아는 정보) +1
    for(int x: smaller[now]){
        small(x); //dfs
    }
}
 
void tall(int now){
    if(chk_tall[now]) return;
    chk_tall[now] = 1;
    cnt++;
    for(int x: taller[now]){
        tall(x);
    }
}

//나눠서 DFS
 
int main(void){
    scanf("%d %d", &n, &m);
    for(int i = 0; i< m; i++){
        scanf("%d %d", &a, &b);
        smaller[b].push_back(a);
        taller[a].push_back(b);
    }
    int ans = 0;
    for(int i = 1; i<= n; i++){
        cnt =0; //
        for(int j = 1; j<= n; j++){
            chk_small[j] = 0;
            chk_tall[j] = 0;
        } 
        tall(i); small(i);
        if(cnt >= n+1) ans++;
        //n명 중 나 빼고 n-1명의 키 정보를 알면 내 키 순서 를 알 수 있음
        //chk_small(i), chk_tall(i) 돌릴 때 나의 키도 체크됨
        //-> 각각 cnt +1 -> cnt>=n-1 + 2 기준
    }
 
    printf("%d", ans);
    return 0;
 
}