[BOJ] ๋ฌธ์ œ์ง‘(1776)

[๋ฐฑ์ค€(BOJ)] ๋ฌธ์ œ์ง‘(1776) C++

๋ฌธ์ œ : BOJ_16437๋ฒˆ ์–‘ ๊ตฌ์ถœ ์ž‘์ „

๋ฌธ์ œ ์„ค๋ช…

์œ„์ƒ์ •๋ ฌ, bfs, ์šฐ์„ ์ˆœ์œ„ ํ

1~N ๋ฒˆ๊นŒ์ง€ ๋ฌธ์ œ๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ์„ธ ๊ฐ€์ง€ ์กฐ๊ฑด์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

(1) N ๊ฐœ์˜ ๋ฌธ์ œ๋Š” ๋ชจ๋‘ ํ’€์–ด์•ผ ๋˜๊ณ 
(2) ๋ฌธ์ œ์— ๋Œ€ํ•œ ์ •๋ณด(M)์— ๋งž๊ฒŒ ์ˆœ์„œ๋Œ€๋กœ ํ’€์–ด์•ผ ๋˜๊ณ ,
(3) ๊ฐ€๋Šฅํ•˜๋ฉด ๋‚ฎ์€ ์ˆ˜์˜ ์‰ฌ์šด ๋ฌธ์ œ๋ถ€ํ„ฐ ํ’€์–ด์•ผ ๋ฉ๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋Š” ์œ„์ƒ ์ •๋ ฌ์„ ์ด์šฉํ•˜์—ฌ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋“ค๋ผ๋ฆฌ์˜ ์œ„์ƒ์„ ํŒŒ์•…ํ•ด์•ผ ๋˜๋Š” ๊ฒƒ๋„ ๋ฌผ๋ก ์ด์ง€๋งŒ,
์ด ๋ฌธ์ œ๋Š” 3๋ฒˆ ๋ฌธ์ œ๊ฐ€ ์ถ”๊ฐ€๋˜๋ฉด์„œ ๊ทธ๋ƒฅ ์œ„์ƒ ์ •๋ ฌ๋กœ๋งŒ์€ ํ’€ ์ˆ˜ ์—†๋Š” ๋ฌธ์ œ๊ฐ€ ๋˜์–ด๋ฒ„๋ฆฝ๋‹ˆ๋‹ค.
์„œ๋กœ ๋ฐฉํ–ฅ์„ฑ์ด ์žˆ๋Š” ๋ฌธ์ œ๋Š” ๊ทธ ์ˆœ์„œ์— ๋งž๊ฒŒ ํ’€์–ด์•ผ ๋˜์ง€๋งŒ,
์„œ๋กœ ๊ฐ„์˜ ๋ฐฉํ–ฅ์ด ์—†๋Š” ๋ฌธ์ œ๋“ค๋ผ๋ฆฌ๋Š” ๋‚ฎ์€ ์ˆ˜์˜ ๋ฌธ์ œ๋ถ€ํ„ฐ ํ‘ธ๋Š” ๊ฒŒ ์ด ๋ฌธ์ œ์˜ ํฌ์ธํŠธ์ž…๋‹ˆ๋‹ค.


Solution

์ด ๋ฌธ์ œ๋Š” ์šฐ์„  bfs์™€ indegree[] ๋ฐฐ์—ด์„ ์ด์šฉํ•œ ์œ„์ƒ ์ •๋ ฌ์„ ํ•ด์•ผ ๋˜๋Š”๋ฐ, ์ด๋•Œ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์ด์šฉํ•ด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๋ฝ‘์•„์ฃผ๋Š” ๊ฒŒ ํ’€์ด ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.
1,2,3,4์˜ ๋ฌธ์ œ๊ฐ€ ์žˆ๊ณ , 4๋ฒˆ์„ 2๋ฒˆ๋ณด๋‹ค ๋จผ์ € ํ’€์–ด์•ผ ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ณธ๋‹ค๋ฉด, 2๋ฒˆ์€ 4์™€์˜ ํ•˜๋‚˜์˜ indegree๊ฐ€ ์‚ฌ๋ผ์ง€๊ธฐ ์ „๊นŒ์ง€ ์šฐ์„ ์ˆœ์œ„ ํ์— ๋“ค์–ด๊ฐ€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
indgree[i]๊ฐ€ 1 ์ด์ƒ์ธ ์ˆ˜๋“ค์€ indegree[i]๊ฐ€ 0์ด ๋˜๊ธฐ ์ „๊นŒ์ง€ ํ์— ๋“ค์–ด๊ฐ€์ง€ ์•Š์œผ๋ฏ€๋กœ, indegree[i]==0์ธ ์ˆ˜๋“ค์ด ์šฐ์„ ์ˆœ์œ„ ํ์— ๋“ค์–ด๊ฐ€๊ณ  ๋‚˜์˜จ ๋’ค์— ์ˆœ์„œ๋Œ€๋กœ ํ์— ๋“ค์–ด๊ฐ€๊ณ  ์ถœ๋ ฅ๋˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.


Description

  1. ์šฐ์„ ์ˆœ์œ„ ํ์—์„œ greater๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ๊ตฌํ˜„
  2. ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ๋“ค์€ pop๊ณผ ๋™์‹œ์— cout์œผ๋กœ ์ถœ๋ ฅ
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int n, m, line[32001];
priority_queue <int, vector<int>, greater<int>> pq; // ์šฐ์„ ์ˆœ์œ„ ํ
vector<int> adj[32001];
int main(void) {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		line[b]++;
	}
	for (int i = 1; i <= n; i++) {
		if (line[i] == 0) pq.push(i);
	}
	while (!pq.empty()) {
		int now = pq.top();
		cout << now << ' ';
		pq.pop(); // cout์ถœ๋ ฅ๊ณผ ํ•จ๊ป˜ pop
		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i];
			line[next]--;
			if (line[next] == 0) pq.push(next); // indegree๊ฐ€ 0์ผ ๋•Œ pushํ•ด์คŒ์œผ๋กœ์จ ๋‘๋ฒˆ ์งธ ์กฐ๊ฑด์„ ๋งŒ์กฑ
		}
	}
	return 0;
}