[백준/C++] 2252번 줄 세우기

백준

---

🤔문제 이해

비교된 학생들은 그 순서대로 줄을 비교되지 않은 학생들은 그냥 랜덤으로 줄을 세우면 되는 문제이다.

---

💡첫번째 아이디어

비교되지 않은 학생들을 먼저 맨 앞에 세워주고 비교된 학생들은 "순서"가 정해지므로 그 학생들을 순서에 맞게 줄을 세우는 방식을 떠올렸다. 그냥 위상정렬 문제.

 

🔥풀이🔥

in_degree의 값이 0인 경우 먼저 queue에 넣어준다.

queue가 빌때까지 pop한 학생의 번호를 출력하고 그 학생 다음으로 줄을 설 수 있는 학생의 in_degree를 -1해줬을 때 in_degree값이 0이라면 queue에 push해준다.

비교된 학생이 중복될 수 있으므로 visited를 이용해 이미 줄을 세운 학생은 무시해준다.

---

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

using namespace std;

int n, m;
vector<vector<int>> v;
int in_degree[32002];
bool visited[32002];
int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    v.resize(n + 2);

    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        in_degree[b]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
            visited[i] = true;
        }
    }

    while (!q.empty()) {
        int now = q.front();
        q.pop();
        cout << now << " ";

        for( int x : v[now]) {
            in_degree[x]--;
            if( in_degree[x] == 0 && !visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
}

 

🔗참고할 문제

https://yulee.tistory.com/23