[PS일지]위상정렬(백준 2252기초, 줄세우기)

오늘 종만북에서 DFS와, 위상정렬, DFS 스패닝 트리 등등... 을 배웠다.

이 시간에 블로그를 쓰다니... 

 

다른 굇수분들의 비해서는 많이 초라하지만

골드 2 기초 위상정렬 문제인 단계별로 풀어보기에 있는 백준 2252번 풀이를 올릴까한다.

 

어쨌든 나는 닉값하는 코딩 새싹이라 많이 못한다.

잡다한 이야기는 각설하고 일단 문제 분석 들어가자

 

 우리가 구해야할 것은 학생이 줄을 서는 순서이다.

무언가 거창한 알고리즘을 써야할 것 같지만 굳이 그런 것은 아니다.

위상정렬이라는 것을 쓰면 된다.

 

위상정렬이란 

순서를 만드는 거라고 보면 된다.

 

당신이 프린터기로 사진을 인쇄한다고 생각해보자

 

1. 잉크를 체운다.

2. 종이를 체운다.

3. 콘센트를 꼿는다.

4. 인쇄버튼을 누른다.

 

대충 이런 순서로 배열되어있다고 하자

 

1번은 무조건 4번보다 먼저해야한다.

2번은 무조건 4번보다 먼저해야한다.

3번은 무조건 4번보다 먼저해야한다.

 

그렇다면 1-4, 2-4, 3-4 형태의 그래프로 표현해보자

그럴시에 이 그래프는 방향성이 있는(유향그래프) 회로가 존재하지 않는 DAG가 된다.

 

위상정렬은 정점(번호)를 일렬로 나열하되, 서로 순서관계를 선으로 표현할때 왼쪽에서 오른쪽으로만 선의 방향이 있어야한다.

이것을 위상정렬하면

1,2,3,4라고나 할까

물론 2,3,1,4도 된다.

4를 제외하면 서로의 순서의 의존하는 의존 관계는 아니기 때문이다.

 

이러한 위상정렬을 구현하는 방법은 간단한 DFS이다.

DFS는 깊이 우선 탐색으로, 이것을 모른다면 구글링하면 정보의 바다에서 잘 찾을 수 있을 것이다.

 

1. DFS를 실행한다.

2. DFS 함수가 끝날 때마다 저장소에 현재 정점을 저장한다.

3. 저장소를 뒤집는다.

 

위상정렬을 배웠으니 이제 문제에 적용하도록 하자

A학생과 B학생의 키를 비교한다고 하면,

A학생은 B학생보다 항상 뒤에 있어야하므로

유향그래프로, A->B와 같이 나타낼 수 있다.

 

딱 느낌 오지않는가? 그렇다 위상정렬이다.

왜 위상정렬이냐면

키를 비교했을 때 앞에 와야하는 학생 A가 있다면 위상정렬을 했을 시 왼쪽에서 오른쪽 방향으로, 역순하지 않는다는

성질에 따라 항상 B가 뒤에 있다.

 

비교한 결과에 포함되지않는 학생은 아무렇게나 쑤셔넣어(?) 주면된다.

다음은 나의 첫번째 코드이다.

 

#include <iostream>
#include <stack>
using namespace std;
bool visit[32000] = {false, }, conn[32000][32000] = {false, };
int n, m;
stack<int>s;
void dfs(int x){
	visit[x] = true;
	int i;
	for(i = 0; i < n; i++){
		if(conn[x][i])if(!visit[i])dfs(i);
	}
	s.push(x);
}
int main() {
	int i, a, b;
	cin >> n >> m;
	for(i = 0; i < m; i++){
		cin >> a >> b;
		conn[a-1][b-1] = true; // a-1 -> b-1의 유향그래프
	}
	for(i = 0; i < n; i++)if(!visit[i])dfs(i);
	while(!s.empty()){
		cout << s.top()+1 << " ";
		s.pop();
	}
}

 

 

메모리 초과가 났다...

그렇다면 동적배열을 대신해서 큐를 사용해보자

 

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
bool visit[32000] = {false, };
queue<int>conn[32000];
int n, m;
stack<int>s;
void dfs(int x){
	visit[x] = true;
	int i;
	while(!conn[x].empty()){
		if(!visit[conn[x].front()])dfs(conn[x].front());
		conn[x].pop();
	}
	s.push(x);
}
int main() {
	int i, a, b;
	cin >> n >> m;
	for(i = 0; i < m; i++){
		cin >> a >> b;
		conn[a-1].push(b-1);
	}
	for(i = 0; i < n; i++)if(!visit[i])dfs(i);
	while(!s.empty()){
		cout << s.top()+1 << " ";
		s.pop();
	}
}

 

맞았다.

 

간단하게 방향성을 부여해준 후 위상정렬 후에 출력한 것이다.

 

그래서 기초문제이다.

 

 

 

새싹은 과학이다.