[2252] 줄세우기 - 위상정렬 ★☆☆ / 복습 ●

[ 문제 ] : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

---

[ 문제 접근 ]

- 위상정렬 문제라는걸 알고 풀어서 그런지 골드 문제 였는데 어렵지가 않았다.

 

위상 정렬은 ① BFS 로 풀던가 / ② DFS 로 풀면 된다.

개인적으로 BFS가 더 직관적이고 쉬워서 BFS로 푼다.

---

[ 최종 코드 ]

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

using std::cout; using std::cin;
using std::vector;
int a, b, n, m;
vector<int> graph[32001];
int indegree[32001];
int visited[32001];


int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);


	cin >> n >> m;
	while (m--) {
		cin >> a >> b;
		graph[a].push_back(b);
		indegree[b]++;
	}
	std::queue<int> q;

	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}
	for (int j = 0; j < n; j++) { // 모든 노드 에 대해
		int current = q.front();
		q.pop();
		cout << current << " ";

		for (int k = 0; k < graph[current].size(); k++) {
			indegree[graph[current][k]]--;
			if (indegree[graph[current][k]] == 0) {
				q.push(graph[current][k]);
			}
		}
        /* 아래 처럼 간단하게 범위 기반 for 루프 돌어주면 깔끔하다
        for (int elem : adjacent[current]) {
			if (--indegree[elem] == 0) {
				answer.push(elem);
			}
		}
        */
	}

	return 0;
}

---

[ Key Point ]

 

👉 위상 정렬로 풀어야겠다 라고 생각할 수 있는게 포인트 였다.

 

👉 indegree ( 진입간선 - 자신에게 오는 간선 ( incoming edge) ) 를 담을 배열을 만들어준다.

한 정점으로 오는 진입 간선을 incoming edge라고 하는데 이 엣지의 개수를 나타내는 배열인 indegree 배열을 만들어줘야한다. => indegree = 0 인 정점을 push 하기 때문에 for 문을 돌 때마다 엣지를 지워주면서 indegree 감소시킨다.

---

[ 다른 사람 풀이 ]

 

ref : https://m.blog.naver.com/ndb796/221240353788