[C++] 백준 2252 줄 세우기

문제 링크

---

www.acmicpc.net/problem/2252

2252번: 줄 세우기

접근 방법

---

이 문제는 가장 기본적인 위상 정렬 문제이다. 

 

이 문제는 크게 3가지 부분으로 나눌 수 있습니다. 

 

1. 입력을 받음과 동시에 indegree체크

2. q에 초기값 담기

3. q의 값을 pop하며, 조건에 해당하는 값을 push

아래에서 자세한 설명을 하겠습니다.

 

1. 입력을 받음과 동시에 indegree체크

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		indegree[b]++;
	}

 

위상정렬은 자신이 무엇인가를 하기 위해 다른 무엇인가가 완료되어야 할 수 있다?

즉, 어떤 일을 하는 순서를 찾는 알고리즘 입니다.

예를 들어, '그냥 기초'를 하기 위해선 완전 기초가 요구되어야 하며, '어려움'을 위해서는 '그냥 기초'가 수행되어야 하고,

'보통'을 위해서는 '완전 기초'와 '진짜 기초'가 모두 수행되어야 합니다. 여기서 indegree는 어떤 노드가 수행되기 위해, 선 수행되어야 하는 노드의 수 입니다. 위의 경우 indegree[완전기초] = 0 , indegree[그냥기초] = 1 , indegree[보통] = 2로 표현 가능합니다.  

 

2. q에 초기값 담기

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0)
			q.push(i);
	}

그럼 가장 먼저 수행가능 한 노드는 어떤 것 일까요? indegree[] = 0인 값들, 즉 자신이 수행되기 위해 선 수행 할 것이 없는 것들입니다. 그러한 값을 q에 담아줍니다.

 

3. q의 값을 pop하며, 조건에 해당하는 값을 push

while (!q.empty()) {

		int now = q.front();
		q.pop();

		cout << now << " ";

		for (int i = 0; i < v[now].size(); i++) {
			if (--indegree[v[now][i]] == 0) {
				q.push(v[now][i]);
			}
		}
	}

 자 이제 q에서 pop한 값을 now라 한다면, 자신을 수행하기 위해 now가 선 수행되어야하는 노드들의 indegree가 줄어들 것이고, indegree가 0이 된다면 선 수행할 것들이 없다는 의미이므로 q에 담아줍니다.  

소스 코드

---

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

using namespace std;

vector<int> v[32001];
int indegree[32001];
int n, m;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
		
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		indegree[b]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {

		int now = q.front();
		q.pop();

		cout << now << " ";

		for (int i = 0; i < v[now].size(); i++) {
			if (--indegree[v[now][i]] == 0) {
				q.push(v[now][i]);
			}
		}
	}
}

개발 환경 : VS2019

질문, 지적 환영합니다!