백준 2458 - 키 순서(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2458

2458번: 키 순서

DFS 혹은 플로이드 워셜을 이용해서 풀 수 있는 문제입니다.

저는 DFS를 이용해 풀었습니다.

자신의 키 순서를 정확히 알기 위해서는 자기보다 작은 학생의 수와 큰 학생의 수의 합이 N-1의 값이 되면 됩니다.

예제 입력에서 4의 경우에는 자기보다 작은 학생은 3명, 큰 학생은 2명이기에 자신이 3번째로 크다는 것을 알 수 있다는 것입니다.

 

따라서 DFS를 통해 자신보다 작은 학생의 수와 큰 학생의 수를 나눠서 구한 뒤, 그 합이 N-1이 되는지 확인해줍니다.

N-1이 된다면 순서를 구할 수 있다는 것임으로 값을 하나 증가해줍니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M, order;
vector<int> down[501]; // 자신보다 작은 학생
vector<int> up[501]; // 자신보다 큰 학생
int check[501];

void dfs(vector<int> v[], int start){
    check[start] = 1;
    for(int i = 0; i < v[start].size(); i++){
        int x = v[start][i];
        if(check[x] == 0){
            check[x] = 1;
            order++;
            dfs(v, x);
        }
    }
}

void solve(){
    int ans = 0;
    for(int i = 1; i <= N; i++){
        order = 0;
        memset(check, 0, sizeof(check));
        dfs(down, i);
        memset(check, 0, sizeof(check));
        dfs(up, i);
        if(order == N - 1) ans++;
    }
    cout << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        down[y].push_back(x);
        up[x].push_back(y);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요