[백준 ACM craft] 위상정렬 문제

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

1005번: ACM Craft

ACM craft라고 starcraft 문제를 비유한 듯한 문제다. 위상정렬문제이지만 단순 위상정렬문제가 아니라 각각의 건물이 지어지는데 걸리는 시간도 고려해야하는 살짝 까다롭다면 까다로울 수 있고 쉽다면 쉬운 문제다.

 

문제 풀 때 고려해야 하는 것 : 

1. 각 노드(구조체)안에 어떤 정보를 담고 있을 것인가?

2. 다음 노드를 가리킬 때 어떤 식으로 가리킬 것인가?

3. 각 노드마다 실행시간(건물건설시간)이 달라서 위상정렬의 indegree를 카운팅하는게 까다로울 수 있는데 어떻게 할 것인가?

4. indegree == 0 인 노드 정보를 어떻게 기록하여 바로 찾아갈 수 있게 할 것인가?

 

 

풀이 :

1. 구조체를 문제 조건상 최대 1000개까지 선언해야 하므로 메모리의 용량을 생각하여 구조체안에 들어가는 정보는 최소화하는 쪽으로 고려하자.

각 구조체안에는 다른 노드가 자기자신을 가리키고 있는지를 나타내는 indegree, 자기 노드가 실행되는데 걸리는 시간(건설시간)을 나타내는 buildTime, 게임이 시작한 시점부터 이전 노드가 실행완료하는데 걸린 시간을 기록하는 preNodeFinishTime만으로 구조체 정보를 마무리한다.

 

2. 원래는 구조체에 포인터를 넣고 다음 노드를 가리키려고 했으나 문제 조건상 한 노드가 여러개의 다음 노드를 가리킬 수도있고, 여러개의 이전 노드가 한개의 다음 노드를 동시에 가리킬수도 있으므로 각각의 노드가 포인터로 연결정보를 표시하는데는 무리가 있다. 이를 해결하기 위해서는 각각의 노드가 포인터배열을 가지고있어야하는데 구조체의 크기가 너무 커지기 때문이다.

개인적으로 문제를 풀기위해 가장 고민했던 부분인데 어설프게 크기가 매우 큰 배열을 미리 선언하고 싶지도 않았기 때문이다. 이를 해결할 수 있는 것은 2차원 벡터다.

[열]에 있는 노드가 [행]에 있는 노드를 가리킨다고 정보를 기록할 수 있고, 문제에 따라 그 크기가 가변적으로 변할 수 있다.

2차원 벡터 사용 예시

2차원 벡터 전체 개략도

3. 이전 노드를 실행할 때마다 이미 기록돼 있는 다음 노드의 preNodeFishTime과 현재노드의 preNodeFishTime + buildTime을 비교하여 값을 업데이트한다. 실제로 컴퓨터가 위상정렬의 indegree를 처리하고 push, pop하는거에 상관없이 preNodeFinishTime은 건설시간에 따라 업데이트 된다.

4. indegree == 0 인 노드를 for문을 이용하여 일일이 찾지말고 indegree == 0인 노드를 매번 큐에 담아놓는다. 탐색 시간을 줄일 수 있다.

 

 

 

배운점 : 

1. 방문표시, 건설완료는 큐, 스택에서 pop할때 한다.

2. 방문표시를 pop하자마자 바로 하기 위해 큐나 스택에 push할때는 필요한 처리는 다 하고 넣는다.(preNodeFinishTime처리, indegree처리 등)

3. 연결정보를 표현할 때 포인터로 표현하기 어려운경우 2차원배열이나 2차원 벡터로 표현할 수 있다.

4. 큐, 스택을 이용하여 찾아가야하는 노드정보를 기록해주면 탐색 시간을 줄일 수 있다.(위상정렬,BFS,DFS)

 

 

 

전체 소스는 다음과 같다.

 

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef struct Node
{
	int indegree;		// 자기자신을 가리키는 노드의 갯수
	int bulidTime;		// 자기자신 노드가 수행하는데 걸리는 시간
	int preNodeFinishTime;	// 시작한 순간부터 이전노드가 수행완료한 시간을 기록
}node;

node building[1001];	// 이건 매 반복문마다 초기화를 안해줘도 된다.
int T, N, K;
int X, Y;
int goal;
queue<int> q;

int main()
{
	scanf("%d", &T);
	while(T--)
	{
		vector<vector > nextNode;		// 2차원벡터 초기화	// 노드간 연결정보를 담고있는 벡터
		nextNode.push_back(vector());	// index맞추기용으로 열 하나 추가

		scanf("%d %d", &N, &K);
		for (int i = 1; i <= N; i++)	// index는 1번부터 매긴다
		{
			nextNode.push_back(vector());	// 건물갯수만큼 열 추가
			scanf("%d", &building[i].bulidTime);	// 건물 짓는데 걸리는 시간 업데이트
			building[i].preNodeFinishTime = 0;
			building[i].indegree = 0;
		}

		for (int i = 0; i < K; i++)
		{
			scanf("%d %d", &X, &Y);
			nextNode[X].push_back(Y);	//노드간 연결정보 업데이트
			building[Y].indegree++; // 포인터 찍히고 있는 갯수 업데이트
		}
		for (int i = 1; i <= N; i++)
		{
			if (building[i].indegree == 0)	// 당장 건물 지을수 있는 노드들 큐에 넣는다
			{
				q.push(i);	// 큐안에는 인덱스정보만 넣는다
			}
		}

		scanf("%d", &goal);	// 목적지 입력

		while (!q.empty())
		{
			int cur = q.front();
			q.pop();	// pop 함으로써 현재노드는 건설을 완성했다고 취급한다.

			if (cur == goal)	// 종료조건 확인 
			{
				int ret = building[goal].preNodeFinishTime + building[goal].bulidTime;
				printf("%d\n", ret);
			}

			for (int i = 0, ii = nextNode[cur].size() ; i < ii; i++)	// 현재 노드가 가리키고 있는 모든 노드에 대해서 실행
			{
				int next = nextNode[cur][i];	// 다음 노드

				if (building[next].preNodeFinishTime < building[cur].preNodeFinishTime + building[cur].bulidTime)
				{
					building[next].preNodeFinishTime = building[cur].preNodeFinishTime + building[cur].bulidTime;	//next노드의 preNodeFinishTime 업데이트
				}

				building[next].indegree--;	// 현재노드를 지었으니 다음 노드의 indegree를 업데이트
				if (building[next].indegree == 0)
				{
					q.push(next);	//indegree가 0 이면 큐에 넣는다
				}
				
				
			}
		}

	}

	return 0;
}