백준 2252(줄 세우기)

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

2252번: 줄 세우기

너무 오랜만에 알고리즘 문제를 풀었다. 

 

역시 관성은 대단하다. 

 

이 문제는 위상정렬의 대표적인 문제로, 위상정렬의 개념을 그대로 적용하면 AC가 나온다

근데 왜 골2인지 의문. 그래프 성질이 들어가서 그런가

 

위상정렬을 하는 이유는 모르겠다. 순서가 있는 순서도에서 순서를 출력하고자 할때에 쓰이는건가 사실 여기서 차수가 필요한데, 그다지 직관적으로 와닿지는 않았다. 

 

만약에 아래와 같은 순서도가 존재한다고 하자

 

일어나기 -> 밥먹기 -> 씻기 -> 운동하기 -> 공부하기 -> 자기(종료)

  -> 이불개기->운동하기 /

 

밥먹기에서 씻기로 가고, 운동하기에서 씻기로 간다고 할때에 

 

단순하게 위 순서도를 보면 일어나서 밥먹거나, 일어나서 이불개고 운동하고 씻거나 둘 중에 하나로 간다고 생각을 하게 된다. 하지만 위상정렬로 출력하게 되면

 

일어나기 -> 밥 or 이불 -> 운동 -> 씻기 -> ... 으로 가게된다

 

운동해야 씻는 순서로 무조건 출력이 되기 때문에, 내 직관과는 많이 달랐다고 할 수 있다. 

 

그렇지만 쓰임에 따라서 달라질 것 같기는 하다. 

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 32050

int num[MAX];
int N, M, a,b;
queue<int> q;
vector<int> nxt[MAX];

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		nxt[a].push_back(b);
		num[b]++;
	}

	for (int i = 1; i <= N; i++) {
		if (num[i] == 0) q.push(i);
	}

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << " ";
		for (int i = 0; i < nxt[x].size(); i++) {
			num[nxt[x][i]]--;
			if (num[nxt[x][i]] == 0) q.push(nxt[x][i]);
		}
	}
}