백준 2252 줄 세우기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

위상 정렬로 풀이되는 대표적인 문제 중의 하나이다.

입력이 pair로 주어지며, (a,b)를 받아서, 아래와 같이 그래프를 구성한다.

cin>>a>>b;
graph[a].push_back(b);
indegree[b]++;

입력을 모두 받은 후, indegree값이 0인 값들을 모두 큐에 집어넣고 (BFS 돌리듯이) 하나씩 빼면서

- 위상정렬된 벡터 등에 push 해주기

- 연결된 정점의 indegree값을 --해주기

- 해당 연결 정점의 indegree값이 0이 되면 그 정점도 큐에 넣어준다.

위의 3가지를 해준다.

 

아래의 예시와 같이 사이클이 없는 단방향 그래프가 있다고 해보자. 이 그래프를 본 문제에 빗대어 본다면,

1이 2보다 작다.

1은 3보다 작다.

3은 4보다 작다.

4는 2보다 작다.

를 의미하게 된다.

위의 그림에 설명한 바와 같이, 1을 가장 먼저 보게 되고, 그다음 3을 보는데, 3을 처리한 후에도 4가 아직 처리되지 않아서,

4에서 2로 들어오는 간선 처리가 안된 상태가 된다(빨간색 표시). 그래서 2를 가장 나중에 보게 되고, 2가 가장 키가 큰 사람이 되는 것이다.

위의 그림 예시에서는 1,2,3,4의 순위를 정확하게 정할 수 있었지만, 모호한 형태가 있을 수 있다. 순위가 정해지지 않는 사람들이 있을 수 있게 된다. 그런 경우를 대비해 문제에서는 여러 개의 답이 있을 수 있다고 한 것이다.

아래 그림은 위의 예시에서 각 정점별로 초기 indegree값이 무엇인지를 나타낸 것이다. 각 사람을 번호 그 자체로 접근하기 위해 배열의 크기는 사람 수 + 1이다. 들어오는 간선이 없는 정점 1 (자신보다 작은 사람이 없는)이 indegree [1]=0 임을 알 수 있고, 여기가 그래프 순회의 시작점이 되는 것이다.

 

기본적인 아이디어는 자기보다 큰 사람이 있으면(자기에 들어오는 간선) 그 사람을 항상 먼저 보고 나서 자신을 본다는 것이다.

위상 정렬의 대한 개략적인 아이디어는 여기를 참조하자.

 

<주요 내용>

위상 정렬, 그래프 순회

 

<코드>

#include <iostream>
#include <queue>
#include <vector>
#define endl '\n'
using namespace std;
const int sz=32e3+1;
int n,m,a,b,ind[sz];
vector<int>graph[sz],order;
queue<int>q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        graph[a].push_back(b);
        ind[b]++;
    }
    for(int i=1;i<=n;++i)if(!ind[i])q.push(i);
    while(!q.empty()){
        int curr=q.front();q.pop();
        order.push_back(curr);
        for(int nx:graph[curr])if(!--ind[nx])q.push(nx);
    }
    for(int i=0;i<(int)order.size();++i)cout<<order[i]<<' ';
    return 0;
}