[BOJ] ACM Craft(1005)

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

๋ฌธ์ œ : BOJ_1005๋ฒˆ ์ด๋ชจํ‹ฐ์ฝ˜

๋ฌธ์ œ ์„ค๋ช…

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

๊ฐ ๊ฑด๋ฌผ๋งˆ๋‹ค ๊ทธ ๊ฑด๋ฌผ์„ ์ง“๊ธฐ ์œ„ํ•ด์„œ ๋จผ์ € ์ง€์–ด์ ธ์•ผ ํ•˜๋Š” ๊ฑด๋ฌผ๋“ค์ด ์กด์žฌํ•˜๊ณ , ๋จผ์ € ์ง€์–ด์•ผ ํ•˜๋Š” ๊ฑด๋ฌผ์ด ์—†๋Š” ๊ฑด๋ฌผ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ์ง€์ •๋œ ๊ฑฐ๋ฌผ์„ ์ง€์„ ๋•Œ๊นŒ์ง€ ๊ฑธ๋ฆฌ๋Š” ์ตœ์†Œ ์‹œ๊ฐ„์„ ์ž‘์„ฑํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
๊ฑด๋ฌผ์— ๋Œ€ํ•œ ์•ž๋’ค ๊ด€๊ณ„๊ฐ€ ์žˆ๊ณ , ์‚ฌ์ดํด์ด ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์— indegree๋ฅผ ์ด์šฉํ•œ ์œ„์ƒ์ •๋ ฌ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
๊ทธ๋ฆฌ๊ณ  ๋จผ์ € ์ง€์–ด์•ผ ํ•˜๋Š” ๋ชจ๋“  ๊ฑด๋ฌผ์ด ์ง€์–ด์ ธ์•ผ ๋‹ค์Œ ๊ฑด๋ฌผ์ด ์ง€์–ด์ง€๋ฏ€๋กœ, dp๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๊ฑด๋ฌผ์ด ์ง€์–ด์งˆ ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ ์‹œ๊ฐ„์„ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Solution

ํ•œ ๊ฑด๋ฌผ์ด ์ง€์–ด์ง€๋Š” ์‹œ๊ฐ„์„ ๋ชจ๋‘ ์ž…๋ ฅ๋ฐ›๊ณ (wait[]), ์ตœ์ข…์ ์œผ๋กœ ๊ทธ ๊ฑด๋ฌผ์ด ์ง€์–ด์งˆ ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ ์‹œ๊ฐ„์— ๋Œ€ํ•œ ๋ฐฐ์—ด์„ ๋งŒ๋“  ๋’ค(res[]), ์œ„์ƒ์ •๋ ฌ์„ ํ†ตํ•ด ์ •์ ์— ๋Œ€ํ•ด ์ด์–ด์ง„ indegree๋ฅผ ์ „๋ถ€ ํƒ์ƒ‰ํ•˜๋ฉฐ ๊ทธ ๊ฑด๋ฌผ์ด ์ง€์–ด์งˆ ์ˆ˜ ์žˆ๋Š” ์‹œ๊ฐ„๋“ค์„ ๊ฑด๋ฌผ๋งˆ๋‹ค ๊ฐ๊ฐ ์ฐพ์•„๋‚ด ๋ฐฐ์—ด์— ๋„ฃ๊ณ , ๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ res ๊ฐ’์„ ์ถœ๋ ฅํ•ด์ฃผ๋Š” ๋ฐฉ์‹์œผ๋กœ ํ’€์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


Description

  1. ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๊ฐ€ ๋๋‚  ๋•Œ๋งˆ๋‹ค ๊ฐ ๋ฐฐ์—ด์„ ์ดˆ๊ธฐํ™”ํ•ด์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค. (memset)
  2. ๋จผ์ € ์ง€์–ด์•ผ ํ•˜๋Š” ๊ฑด๋ฌผ์ด ์—†๋Š” ๊ฑด๋ฌผ๋“ค์€ ๊ทธ ๊ฑด๋ฌผ์ด ์ง€์–ด์ง€๋Š” ์‹œ๊ฐ„ ์ž์ฒด๊ฐ€ ์ตœ์†Œ ์‹œ๊ฐ„์œผ๋กœ ์ง€์–ด์งˆ ์ˆ˜ ์žˆ๋Š” ์‹œ๊ฐ„์ด๋ฏ€๋กœ, indegree[i] == 0 ์ธ i ๋ฒˆ ์งธ ๊ฑด๋ฌผ๋“ค์€ ๋ชจ๋‘ res[i] = wait[i];๋กœ ํ• ๋‹นํ•ด์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int main(void) {
	int roof;
	cin >> roof;
	for (int i = 0; i < roof; i++) {
		vector<int>adj[1001];
		queue<int>q;
		int n, m, indegree[1001] = { 0, }, res[1001], wait[1001];
		memset(indegree, 0, sizeof(indegree)); // ํ…Œ์ŠคํŠธ์ผ€์ด์Šค ๋งˆ๋‹ค memset์œผ๋กœ ์ดˆ๊ธฐํ™”
		memset(res, 0, sizeof(res));
		memset(wait, 0, sizeof(wait));
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> wait[i];
		}
		for (int i = 1; i <= m; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			indegree[b]++; // ์ „ํ›„ ๊ด€๊ณ„๋ฅผ ์—ฐ๊ฒฐํ•  ๋•Œ ๋งˆ๋‹ค indegree[]๋ฅผ ์˜ฌ๋ ค์ค๋‹ˆ๋‹ค.
		}
		int fin;
		cin >> fin;
		for (int i = 1; i <= n; i++) {
			if (indegree[i] == 0) q.push(i);
			res[i] = wait[i];
		}
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			for (int i = 0; i < adj[now].size(); i++) {
				int next = adj[now][i];
				res[next] = max(res[next], res[now] + wait[next]); // max()๋ฅผ ์ด์šฉํ•ด ๋ชจ๋“  indegree๋ฅผ ํ™•์ธํ•ด์ฃผ๊ณ  ๊ทธ ์ค‘ ์ตœ๋Œ“๊ฐ’์„ res[i]์— ํ• ๋‹นํ•ฉ๋‹ˆ๋‹ค.
				indegree[next]--;
				if (indegree[next] == 0) q.push(next);
			}
		}
		cout << res[fin] << endl;
	}
	return 0;
}