[백준 2252] 줄세우기

문제요약

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

아이디어

음.. 사실 위상정렬 문제가 풀고싶어서 찾은 문제였고, 위상정렬로 풀어야한다는 걸 알고 있었다.

그래도 위상정렬이 적용가능한 이유를 얘기해보자면...

• n 개 노드에 대한 (키)순서 비교(edge)를 일부 제공했다.
• 키라는 관계는 절대적 비교가 가능하므로 (a->b, b->c 면 c->a가 성립할 수 없다) DAG에 해당하고, 문제에선 DAG의 모든 엣지를 주진 않았다.
• DAG를 전부 알려준 건 아니지만, 문제는 자기가 준 DAG 엣지만 위반하지 않으면 정답처리한다 했다.(중복정답 허용)

배운 것

memset 함수를 요즘 애용하는데, string.h 혹은 memory.h에 정의돼있다.
string.h에 memset, memcpy, memcmp, memmove 함수가 있다고 한다..
memmove는 string.h에만 정의 돼있고, memory.h엔 정의돼있지 않다고 한다.

소스코드

#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
int main() {
	int n,m;
	cin >> n >> m;
	int a, b;

	int incoming[32001];
	vector<int> g[32001];//incoming edge
	memset(incoming, 0, sizeof incoming);
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		incoming[b]++;
	}

	queue<int> q;
	//줄을 못세우는 경우는 고려하지 x
	for (int i = 1; i <= n; i++) {
		if (incoming[i] == 0) q.push(i);
	}
	
	for (int i = 1; i <= n; i++) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int j = 0; j < g[cur].size(); j++) {
			int ad = g[cur][j];
			if (--incoming[ad] == 0) q.push(ad);
		}
	}
}

잡담

아.. 너무.... 졸려..... 살려줘.............

어깨도 아퍼... 안마의자 사줘............