BOJ 1005 : ACM Craft

알고리즘 문제 전체 링크

 

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

 

 

위 그림에서 2번, 3번 건물은 1번 건물이 완료되어야 건설을 시작할 수 있다.

4번 건물은 2번, 3번 건물이 완료되어야 건설을 시작할 수 있다.

 

따라서 각 node에 들어오는 화살표 (in-degree)가 작은 순서대로 건설이 시작된다.

이런 문제는 위상 정렬을 이용해서 풀 수 있다.

 

1번의 경우에는 들어오는 화살표가 없으므로 in-degree가 0이다.

2, 3번의 경우는 in-degree가 1이며, 4번은 2가 된다.

---

입력받을 변수와 in-degree를 저장할 배열, 그리고 건설 시간을 저장할 배열, 답을 저장할 배열을 선언한다.

ans[node] = 해당 node 건물이 완료될 때 까지 걸린 시간이다.

#define MAX (1010)

int T, N, K, X, Y, W;

int indegree[MAX];
int time[MAX];
int ans[MAX];

 

메모리 풀 방식으로 각 node를 연결한다.

typedef struct st
{
	int value;
	struct st *next;
}NODE;

NODE HEAD[MAX];
NODE POOL[100100];
int pcnt;

void Make(int p, int c)
{
	NODE *nd = &POOL[pcnt++]; /* POOL에서 메모리를 가져온다 */
	nd->value = c; /* node에 값을 설정. */

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

 

Make를 이용하여 node를 만들 때, parent → childern만 연결한다.

위 그림에서 1번 건물 건설은 완료한 후, 2번과 3번 건설을 시작하지, 2번이 1번으로 가지는 않기 때문이다.

 

따라서 input은 아래와 같이 구현된다.

tc가 여러 개인 문제이므로 초기화 코드가 필요하다.

그리고 자식 node에서 indegree를 증가시킨다.

void input()
{
	scanf("%d %d", &N, &K);
	
	/* 초기화 */
	rp = wp = pcnt = 0;

	for (int i = 1; i <= N;i++)
	{
		scanf("%d", &TIME[i]);
		ANS[i] = indegree[i] = 0;
		HEAD[i].next = 0;
	}

	for (int i = 0; i < K;i++)
	{
		scanf("%d %d", &X, &Y);

		Make(X, Y);
		indegree[Y]++;
	}

	scanf("%d", &W);
}

 

main에서 input을 받은 후, indegree가 0인 node부터 queue에 담아서 BFS를 실행하면 된다.

int main(void)
{
	scanf("%d", &T);

	for (int tc = 0; tc < T;tc++)
	{
		input();

		for (int i = 1; i <= N;i++)
			if (indegree[i] == 0) queue[wp++] = i;

		BFS();

		printf("%d\n", ans[W]);
	}

	return 0;
}

 

queue에서 빠져나온 node는 건설이 완료된 node이므로 ans[node]에 time을 누적한다.

그리고 out에서 연결된 node 중 indegree가 0이 되는 경우만 queue에 다시 담는다.

(out의 node를 만나면 indegree는 1 감소 시켜야 한다.)

 

건물 건설 시간은 out된 node들의 건설 완료 시간 중 최대가 되므로 max를 갱신해야 한다.

문제에 주어진 그림도 4번 건물이 완성되려면 10(1번) + 100(2번, 3번 중 큰 값) + 10(4번) = 120이 된다.

void BFS()
{
	while (wp > rp)
	{
		int out = queue[rp++];

		ans[out] += time[out];

		if (out == W) return;

		for (NODE* p = &HEAD[out]; p != NULL; p = p->next)
		{
			int tmp = p->value;
			
			indegree[tmp]--;
			
			if (indegree[tmp] == 0) queue[wp++] = tmp;

			ans[tmp] = max(ans[tmp], ans[out]);
		}
	}
}

모든 건물을 지을 필요는 없고, 목표 건물인 W가 지어지면 종료하면 된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (1010)

int T, N, K, X, Y, W;

int indegree[MAX];
int time[MAX];
int ans[MAX];

typedef struct st
{
	int value;
	struct st *next;
}NODE;

NODE HEAD[MAX];
NODE POOL[100100];
int pcnt;

int queue[100100];
int rp, wp;

void Make(int p, int c)
{
	NODE *nd = &POOL[pcnt++]; /* POOL에서 메모리를 가져온다 */
	nd->value = c; /* node에 값을 설정. */

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

void input()
{
	scanf("%d %d", &N, &K);
	
	/* 초기화 */
	rp = wp = pcnt = 0;

	for (int i = 1; i <= N;i++)
	{
		scanf("%d", &time[i]);
		ans[i] = indegree[i] = 0;
		HEAD[i].next = 0;
	}

	for (int i = 0; i < K;i++)
	{
		scanf("%d %d", &X, &Y);

		Make(X, Y);
		indegree[Y]++;
	}

	scanf("%d", &W);
}

int max(int a, int b)
{
	return (a > b) ? a : b;
}

void BFS()
{
	while (wp > rp)
	{
		int out = queue[rp++];

		ans[out] += time[out];

		if (out == W) return;

		for (NODE* p = &HEAD[out]; p != NULL; p = p->next)
		{
			int tmp = p->value;
			
			indegree[tmp]--;
			
			if (indegree[tmp] == 0) queue[wp++] = tmp;

			ans[tmp] = max(ans[tmp], ans[out]);
		}
	}
}

int main(void)
{
	scanf("%d", &T);

	for (int tc = 0; tc < T;tc++)
	{
		input();

		for (int i = 1; i <= N;i++)
			if (indegree[i] == 0) queue[wp++] = i;

		BFS();

		printf("%d\n", ans[W]);
	}

	return 0;
}