[ 백준 ] 2458 / 키 순서

金弘均·2021년 9월 14일
0

Baekjoon Online Judge

목록 보기
4/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2458 / 키 순서
 * 
 * Kind :: BFS
 *
 * Insight
 * - 자신의 키가 몇 번째인지 정확히 알 수 있으려면
 *   자기보다 키가 작은 학생들의 수 + 자기보다 키가 큰 학생들의 수 + 1(자신) 의 값이
 *   전체 학생 수와 같아야 한다
 *   + 문제의 입력처럼 두 양의 정수 a와 b가 주어졌을 때
 *     a인 학생이 번호가 b인 학생보다 작은 것을 a -> b 방향으로 그래프를 그려주면
 *     이 그래프를 바탕으로 a를 시작점으로 하는 BFS 를 돌려서
 *     a 보다 키가 큰 학생들의 수를 구할 수 있다
 *     # 반대로 키가 작은 학생들의 수는 a <- b 방향으로 그래프를 그려주어서
 *       이 그래프를 바탕으로 a를 시작점으로 하는 BFS 돌려서
 *       a 보다 키가 작은 학생들의 수를 구할 수 있다
 *
 * Point
 * - 매번 BFS 를 돌리는 것이 비효율적인 것 같아 DP 를 적용할까 싶었으나 예외가 존재한다
 *   + 문제 설명의 그래프에서 2번 학생보다 키가 작은 학생들의 수를 구하려고 BFS 를 돌릴 때
 *     dp[4] + dp[5] 로 계산하게 되는데
 *     dp[4] = dp[3] + dp[5] 이므로
 *     dp[5] 가 중복되어 체크된다
 *     # BFS 한번 도는데 O(N+M) 이니 총 시간복잡도는 O(N*(N+M)) 이며
 *       결국 O(N^3) 인데 N=500 이라 아슬아슬하다고 생각했는데 다행히 괜찮았다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, M;
    cin >> N >> M;
    vector<int> I[N+1], O[N+1];
    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        I[a].push_back(b); /* a -> b */
        O[b].push_back(a); /* a <- b */
    }

    // Process
    bool isVisited[N+1];

    int ans = 0;
    for (int i=1; i<=N; i++) {

        memset(isVisited, false, sizeof(isVisited)); /* 방문 초기화 */
        int cnt_t = 0; /* i번 학생보다 키가 큰 학생들의 수 */
        queue<int> T;
        for (int t : I[i]) { T.push(t); isVisited[t] = true; }
        while (not(T.empty())) {
            int c = T.front();
            T.pop();
            cnt_t++;
            for (int n : I[c]) {
                if (not(isVisited[n])) {
                    isVisited[n] = true;
                    T.push(n);
                }
            }
        }

        memset(isVisited, false, sizeof(isVisited)); /* 방문 초기화 */
        int cnt_s = 0; /* i번 학생보다 키가 작은 학생들의 수 */
        queue<int> S;
        for (int s : O[i]) { S.push(s); isVisited[s] = true; }
        while (not(S.empty())) {
            int c = S.front();
            S.pop();
            cnt_s++;
            for (int n : O[c]) {
                if (not(isVisited[n])) {
                    isVisited[n] = true;
                    S.push(n);
                }
            }
        }

        /* 전체 학생들의 수 =
         * 자신보다 키가 작은 학생들의 수 + 자신보다 키가 큰 학생들의 수 + 1(자신)
         * 이라면 */
        if (cnt_s + cnt_t + 1 == N) {
            ans++; /* 자신의 키가 정확히 몇 번째인지 알 수 있음 */
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글