[BOJ] ์ค„ ์„ธ์šฐ๊ธฐ(2252)

[๋ฐฑ์ค€(BOJ)] ACM Craft(2252) C++

๋ฌธ์ œ : BOJ_2252๋ฒˆ ์ค„ ์„ธ์šฐ๊ธฐ

๋ฌธ์ œ ์„ค๋ช…

์œ„์ƒ์ •๋ ฌ, bfs

์œ„์ƒ์ •๋ ฌ์„ ์ด์šฉํ•ด์„œ ์ˆœ์„œ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๊ธฐ๋ณธ์ ์ธ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. N ๋ช…์˜ ํ•™์ƒ ์ค‘ ์„œ๋กœ ์ค„์„ ์„ธ์šด M ๊ฐœ์˜ ๊ฒฝ์šฐ์˜ ์ˆœ์„œ๋งŒ ๊ณ ๋ คํ•˜๊ณ  ์ค„์„ ์„ธ์šด ๊ด€๊ณ„๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด ์•„๋ฌด ์ˆœ์„œ๋‚˜ ์ƒ๊ด€์—†์ด ์ถœ๋ ฅํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Solution

์ˆœ์„œ๋Œ€๋กœ ๋ฐฐ์—ดํ•˜๊ธฐ ์œ„ํ•ด indegree๋ฅผ ์ด์šฉํ•œ ์œ„์ƒ์ •๋ ฌ์„ ํ•ด์ค˜์•ผ ํ•˜๋ฏ€๋กœ, indegree๋ผ๋Š” ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ์ˆœ์„œ๋ฅผ ๋ฒกํ„ฐ์— ์—ฐ๊ฒฐํ•ด์ค„ ๋•Œ๋งˆ๋‹ค ๋ฐฐ์—ด์˜ ์ˆ˜๋ฅผ ์˜ฌ๋ ค์ฃผ๋ฉฐ, ํ์— ์ง‘์–ด๋„ฃ์„ ๋•Œ๋Š” ๋“ค์–ด์˜ค๋Š” ๋ชจ๋“  ๊ฐ„์„ ์„ ํƒ์ƒ‰ํ•œ ๊ฒฝ์šฐ์—๋งŒ push ํ•ด์ฃผ๋Š” ๋ฐฉ์‹์œผ๋กœ ์†Œ์Šค๋ฅผ ์งœ์•ผ ํ•ฉ๋‹ˆ๋‹ค.


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int stu, rel, indegree[32001], st[32001], cnt;
vector<int> adj[32001];
queue<int>q;
int main(void) {
	cin >> stu;
	cin >> rel;
	for (int i = 0; i < rel; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		indegree[b]++;
	}
	int start;
	for (int i = 1; i <= stu; i++) {
		if (indegree[i] == 0) {
			cnt++;
			st[cnt] = i;
		}
	}
	for (int i = 1; i <= cnt; i++) {
		q.push(st[i]);
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			printf("%d ", now);
			for (int i = 0; i < adj[now].size(); i++) {
				int next = adj[now][i];
				indegree[next]--; // ํƒ์ƒ‰ ํ›„ ๋“ค์–ด๊ฐ„ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ฐ์†Œ์‹œํ‚จ๋‹ค.
				if (indegree[next] == 0) {
					q.push(next); // ๋“ค์–ด๊ฐ„ ๊ฐ„์„ ์˜ ์ˆ˜๊ฐ€ 0์ด ๋œ ๊ฒฝ์šฐ์—๋งŒ push
				}
			}
		}
	}
	return 0;
}