[BOJ] 줄 세우기(2252)

[백준(BOJ)] ACM Craft(2252) C++

문제 : BOJ_2252번 줄 세우기

문제 설명

위상정렬, bfs

위상정렬을 이용해서 순서를 출력하는 기본적인 문제입니다. N 명의 학생 중 서로 줄을 세운 M 개의 경우의 순서만 고려하고 줄을 세운 관계가 아니라면 아무 순서나 상관없이 출력할 수 있습니다.

---

Solution

순서대로 배열하기 위해 indegree를 이용한 위상정렬을 해줘야 하므로, indegree라는 배열을 만들어 순서를 벡터에 연결해줄 때마다 배열의 수를 올려주며, 큐에 집어넣을 때는 들어오는 모든 간선을 탐색한 경우에만 push 해주는 방식으로 소스를 짜야 합니다.

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int stu, rel, indegree[32001], st[32001], cnt;
vector<int> adj[32001];
queue<int>q;
int main(void) {
    cin >> stu;
    cin >> rel;
    for (int i = 0; i < rel; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        indegree[b]++;
    }
    int start;
    for (int i = 1; i <= stu; i++) {
        if (indegree[i] == 0) {
            cnt++;
            st[cnt] = i;
        }
    }
    for (int i = 1; i <= cnt; i++) {
        q.push(st[i]);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            printf("%d ", now);
            for (int i = 0; i < adj[now].size(); i++) {
                int next = adj[now][i];
                indegree[next]--; // 탐색 후 들어간 간선의 개수를 감소시킨다.
                if (indegree[next] == 0) {
                    q.push(next); // 들어간 간선의 수가 0이 된 경우에만 push
                }
            }
        }
    }
    return 0;
}