백준 1005번 ACM Craft

🔒[문제 url]

https://www.acmicpc.net/problem/1005

🔑알고리즘

순서가 정해진 그래프? 위상정렬
반복되는 부분 문제를 통한 $i$번 건물을 짓기까지의 최소 시간? DP

• dp[i] : $i$번 건물을 짓기까지의 최소 시간
  • 위상정렬을 진행하며, 모든 건물에 대해 해당 건물 $i$을 짓기까지의 최소 시간을 저장한다.
    이때 최소 시간은 문제 조건에 따라
    해당 건물을 짓기 위해 지어야하는 건물 중 가장 오래 걸리는 건물을 짓기까지의 시간 + $Di$
    가 된다.
    위 사진의 경우, 4번을 짓기 위해선 2(11초) 3번(110초)을 모두 지어야하므로4번 건물을 짓기까지의 최소 시간은 110초 + 10초 = 120초가 된다.

🐾부분 코드

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	// 건설 소요시간
	for (int i = 1; i <= n; i++)
	{
		int time; cin >> time;
		TIME[i] = time;
	}
	// 규칙
	for (int i = 0; i < k; i++)
	{
		int s, e; cin >> s >> e;
		graph[s].push_back(e);
		inDegree[e]++;
	}
	// 승리 건물
	cin >> w;
}

<입력 함수>
위상 정렬을 위한 그래프이므로 각 노드에 대해 진입 차수inDegree를 count한다.

void topology()
{
	// 진입 차수가 0인 정점 q에 push
	for (int i = 1; i <= n; i++)
	{
		if (!inDegree[i]) q.push(i);
		dp[i] = TIME[i];
	}

	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int j = 0; j < graph[now].size(); j++)
		{
			int next = graph[now][j];
			inDegree[next]--;
			dp[next] = max(dp[next], dp[now] + TIME[next]);

			if (!inDegree[next]) q.push(next);
		}
	}
}

<위상 정렬 및 dp 갱신 함수>
위에서 설명한 알고리즘에 따라, dp 갱신 값은

dp[next] = max(dp[next], dp[now] + TIME[next]);

가 된다.

void SOLVE()
{
	cin >> t;
	while (t--)
	{
		// 초기화 및 입력
		for (int i = 1; i <= n; i++)
		{
			graph[i].clear();
			inDegree[i] = 0;
			dp[i] = 0;
		}
		INPUT();

		// 위상정렬
		topology();

		cout << dp[w] << '\n';
	}
	
}

<테스트케이스 반복 및 초기화 함수>
테스트케이스를 반복할때는 반드시 변수를 초기화해주도록 하자.
w번 건물을 지으면 승리하므로, dp[w]를 출력한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <stdio.h> // c
#include <string>
#include <memory.h> // memset
#include <algorithm>
#include <cmath>
// 자료 구조
#include <queue>
#include <vector>
using namespace std;

int t, n, k, w;
vector<int> TIME(1001);
vector<int> inDegree(1001);
vector<int> graph[1001];
queue<int> q;
int dp[1001]{ 0, };

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	// 건설 소요시간
	for (int i = 1; i <= n; i++)
	{
		int time; cin >> time;
		TIME[i] = time;
	}
	// 규칙
	for (int i = 0; i < k; i++)
	{
		int s, e; cin >> s >> e;
		graph[s].push_back(e);
		inDegree[e]++;
	}
	// 승리 건물
	cin >> w;
}

void topology()
{
	// 진입 차수가 0인 정점 q에 push
	for (int i = 1; i <= n; i++)
	{
		if (!inDegree[i]) q.push(i);
		dp[i] = TIME[i];
	}

	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int j = 0; j < graph[now].size(); j++)
		{
			int next = graph[now][j];
			inDegree[next]--;
			dp[next] = max(dp[next], dp[now] + TIME[next]);

			if (!inDegree[next]) q.push(next);
		}
	}
}


void SOLVE()
{
	cin >> t;
	while (t--)
	{
		// 초기화 및 입력
		for (int i = 1; i <= n; i++)
		{
			graph[i].clear();
			inDegree[i] = 0;
			dp[i] = 0;
		}
		INPUT();

		// 위상정렬
		topology();

		cout << dp[w] << '\n';
	}
	
}

int main()
{
	//INPUT();

	SOLVE();
}

🥇문제 후기

문제 하나하나마다 포스팅시 반복되는 알고리즘을 일일히 설명할 수 없다는 한계점을 깨닫는 요즘이다. 포스팅에 지치기 전에, 틈틈이 알고리즘 설명글도 업로드 해야겠다.