백준 2252 줄 세우기 <위상 정렬>

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

<줄 세우기>

 이 문제는 위상 정렬로 푸는 문제로, STACK을 이용한 DFS 알고리즘을 통해 풀 수 있고, queue를 이용하여 degree 1차원 배열을 이용해서도 풀 수 있다.

위상 정렬에 대한 개념은, http://jason9319.tistory.com/93 << 링크의 글을 통해서 이해했다. 이해하기 쉽게 글을 쓰셔서, 이해하는데 어려움이 없었다.

나는 두 가지 방법 중 queue와 indgree 배열을 이용한 문제 풀이가 더 익숙했는데, 이 기회에 DFS로 푸는 방법에 대해 배우게 된 좋은 계기가 되었다.

 indgree를 이용한다는 것은, 특정 노드가 탐색 되기 이전에, 먼저 탐색되어야 하는 노드가 몇개인지 저장해 두는 것이다.

예를 들어 2번 노드를 탐색하기 위해서 1번 노드와 3번 노드를 먼저 탐색해야 한다면, 2번 노드의 indgree는 2가 된다.

줄 세우기 문제의 예시 입력을 보면, 1번 학생은 3번 학생의 앞에 서야 하는 것, 2번 학생은 3번 학생 앞에 서야하는 것을 알 수 있다.

이는, 1번과 2번 학생의 indgree는 1이 되고, 3번 학생의 indgree는 0이 되는 것이다.

queue에 indgree가 0인 학생들을 모두 넣고, 하나씩 꺼내면서 꺼낸 학생의 앞에 서야하는 학생들의 indgree를 1씩 감소시켜주면 된다.

꺼낸 학생은 줄을 섰음을 표시해야 하므로 indgree를 -1로 저장해주면 간단히 해결된다.

꺼낸 학생은 다른 배열에 순서대로 저장하고, 출력해줄 때 역순으로 출력해주면 알맞은 순서로 줄 세우기가 가능하다.

1. queue를 이용한 문제 풀이

#include <iostream>
#include <vector>
#include <queue>

#define SIZE 32001

using namespace std;
int n, m;

vector<int> student[SIZE];
int dg[SIZE];
int arr[SIZE];
int arr_idx = 0;

void solution()
{
	queue<int> s;
	for (int i = 1; i <= n; i++)
	{
		if (!dg[i])
		{
			s.push(i);
		}
	}

	while (!s.empty())
	{
		int cur_s = s.front();
		// 방문 표시
		dg[cur_s] = -1;
		s.pop();
		// 순서 저장 
		arr[arr_idx++] = cur_s;

		for (int x : student[cur_s])
		{
			// indgree 감소 
			--dg[x];
			 
			if (dg[x] == 0)
			{
				// 줄을 설 수 있는 학생이므로,  queue에 넣어준다 
				s.push(x);
			}
		}
	}
	
	// 역순으로 출력 
	for (int i = arr_idx - 1; i >= 0; --i)
	{
		cout << arr[i] << " ";
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	student.resize(n + 1);
	for (int i = 0; i < m; ++i)
	{
		int front, back;
		cin >> front >> back;
		
		student[back].push_back(front);
		
		// indgree 증가 
		++dg[front];
	}

	solution();

	return 0;
}

2. DFS를 이용한 풀이

 

#include <iostream>
#include <stack>
#include <vector>
#define SIZE 32000

using namespace std;
int n, m;
int visit[SIZE + 1];
int arr[SIZE + 1];
vector< vector<int> > student;

void DFS(int node, stack<int> &s)
{
	visit[node] = true;
	for (int x : student[node])
	{
		if (!visit[x])
			DFS(x, s);
	}
	// 더 이상 선행 정점이 없는 경우 push
	s.push(node);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	student.resize(n + 1);
	for (int i = 0; i < m; ++i)
	{
		int front, back;
		cin >> front >> back;

		student[front].push_back(back);
	}
	stack<int> s;
	for (int i = 1; i <= n; ++i)
	{
		if (!visit[i])
		{
			DFS(i, s);
		}
	}

        // 걸어둔 블로그 링크의 코드 스타일을 따라함

	while (s.size())
	{
		cout << s.top() << " ";
		s.pop();
	}

	return 0;
}