글 읽기 - 유사 DFS 방식으로 했는데 틀렸다고 나오네요..(예제는 맞음) 도움부탁드립니다.

blackco 5년 전 0

건물이 건축되는 시간을 역으로 계산했습니다. (역 DFS?) 다음은 알고리즘에 대한 설명입니다.

가장 마지막으로 건축되는 건물W에 대해 timeOfConstruction[W] = time[W]로 시작하여

그 전 건축물의 건축시간을 timeOfConstruction[preW] = timeOfConstruction[W] + time[preW]으로 계산하였으며

필요건축물이 없는 건축물까지 계산하도록 하였습니다. (A건축물 -> B건축물: A는 B의 필요건축물)

이 과정에서 특정 건물은 두 번이상 계산되는 경우가 발생하는데,(대표 예제의 1번 건축물//1->2->4 & 1->3->4: 2번 계산됨)

그러한 경우에는 기존값과 새로 계산되는 값 중 큰 쪽을 택했습니다. (critical pass의 개념으로 보면 될 거 같습니다.)

전체계산이 끝난 후 timeOfConstruction에 계산된 모든 값 중 가장 큰 값을 정답으로 택했습니다.

이렇게 했는데 며칠간 계속 틀렸다고 나오네요...

도움 부탁드립니다.. 감사합니다.

//1005
#include<iostream>
#include<vector>

void FindConstructionTime(int* timeOfConstruction, std::vector<int> order[], 
                          const int to, const int from, const int* time)
{
	if (to != -1)
	{
        //find max
		timeOfConstruction[from] =
			timeOfConstruction[from] > timeOfConstruction[to] + time[from] ?
			timeOfConstruction[from] : timeOfConstruction[to] + time[from];
	}
	else // 최종 건물 W의 경우
	{
		timeOfConstruction[from] = time[from];
	}
    
	while (order[from].empty() == false)
	{
		FindConstructionTime(timeOfConstruction, order, 
                             from, order[from].back(), time);
		order[from].pop_back();
	}
}
int main()
{
	int t;
	scanf("%d", &t);
	for (int tc = 0; tc < t; tc++)
	{
		//입력--------------------------
        int n, k;
		scanf("%d %d", &n, &k);
		int* time = new int[n];
		int* timeOfConstruction = new int[n];
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &time[i]);
			timeOfConstruction[i] = 0;
		}

		std::vector<int> order[1001];

		for (int i = 0; i < k; i++)
		{
			int from, to;
			scanf("%d %d", &from, &to);
			from--;
			to--;
			order[to].push_back(from);
		}
		int w;
		scanf("%d", &w);
		w--;
		//건축시간 계산----------------------
        FindConstructionTime(timeOfConstruction, order, -1, w, time);
		
        //최종 건축시간 중 critical pass를 찾는다. 
        int max = 0;
		for (int i = 0; i < n; i++)
		{
			if (max < timeOfConstruction[i])
			{
				max = timeOfConstruction[i];
			}
		}
		printf("%d\n", max);
		
        if (time) delete time;
		if (timeOfConstruction) delete timeOfConstruction;
	}
	return 0;
}

djm03178 5년 전 1

한 번 방문한 후 간선을 모두 지워버리기 때문에 추후에 더 큰 시간으로 재방문했을 때 그 이후 정점에 도달하지 못합니다.

https://ideone.com/Q4uv1R

blackco 5년 전 0

미처 그부분까지 생각을 못했네요... djm03178님의 많은 답변을 보며 대단하시다는 생각을 했지만 헛점을 금방 찾아내시는 예리함에 재차 감탄합니다.

blackco 5년 전 0

이렇게 해서 틀린 문제는 해결했지만 다시 시간 초과가 뜨네요 ㅎㅎㅎ ㅠ

이 부분은 다시 한 번 고민해봐야겠습니다...ㅎ

아무튼 막혔던 문제는 해결됐으니 질문은 '해결'로 바꾸어두겠습니다!

댓글을 작성하려면 로그인해야 합니다.