[BOJ] 줄세우기

[문제]

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

[풀이]

2252

맞았습니다!!

3920

28

C++14 / 수정

1085

4초 전

 

1) 위상정렬 큐 사용 

 

2) larger[MAX_N] => 다른 사람과 비교하여 인덱스의 주인공이 큰 횟수를 저장 

larger[] == 0 이 되면 다른 사람보다 크지 않다 라는 의미이기 때문에 큐에서 꺼내준다. 

 

3) indegree 백터 배열은 각 인덱스 주인공 마다 자신보다 큰 사람들을 저장한다. 

(큐를 돌 때 한 명씩 꺼내서 larger를 줄여줘야 하기 때문에)

 

#include <iostream>
#include <vector>
#include <queue>
 
#define MAX_N 32001
using namespace std;
 
//줄 세우기 -위상정렬 큐 사용
int larger[MAX_N];
vector<int> indegree[MAX_N];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
 
    cin >> n >> m; //학생 수, 비교한 횟수
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b; // a < b
 
        larger[b]++;
        //다른 사람보다 키가 큰 횟수만큼 증가
        indegree[a].push_back(b); //a와 비교한 사람들을 저장한다
    }
 
    queue<int> q;
 
    for (int i = 1; i <= n; i++)
    {
        if (larger[i] == 0)
        {
            //키가 다른 사람보다 큰 적이 없는 사람
            q.push(i);
        }
    }
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        cout << now << " ";
        //키가 다른 사람보다 크지 않는 사람들을 출력한다.
 
        for (int i = 0; i < indegree[now].size(); i++)
        {
            int next = indegree[now].at(i);
            larger[next]--;
            if (larger[next] == 0) {
                q.push(next);
            }
        }
    }
    return 0;
}