글 읽기 - 두 코드의 결과가 다른 이유가 뭘까요?

rkdgh98 3년 전 0

위 코드는 dfs를 사용하여 위상정렬로 건물 지을 순서를 큐에 담아서 차례대로 시간을 구하는 코드입니다

아래 코드는 1번 건물부터 차례대로 root로 놓고, 트리모양으로 각 건물마다 테크트리를 만들어서 아래서부터 차례대로 지으며 올라오는 식으로 구현했습니다.

위 코드는 정답이 떴고, 아래코드는 오답이 떴습니다.

제 생각에는 결국 두 코드 모두 dfs를 통해 정답을 올바르게 구하는 것처럼 보이는데, 왜 위코드는 정답이 뜨고 아래코드는 틀렸습니다가 나오는지 이해가 가지 않습니다.

짐작으로는 아래 코드에서 건물 500개가 테크트리 역순으로 입력이 주어지면 재귀함수를 너무 많이 들어가서 그런건가 싶기도 합니다만 그것이 정확한 이유인지는 확신이 들지 않아서 질문 올려봅니다.

//위상정렬을 통해 구한 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, buildtime[501], ans[501];
vector<int> v[501]; //v[i] : i 건물이 지어지기 위해 먼저 지어져야 하는 건물벡터
queue<int> q; //위상정렬 결과 담은 큐
int chk[501];

void dfs(int now)
{
	if (chk[now]) return;
	chk[now]++;
	int si = v[now].size();
	for (int i = 0; i < si; i++)
	{
		dfs(v[now][i]);
	}
	q.push(now);
	return;
}

void topological_sort()
{
	for (int i = 1; i <= N; i++)
	{
		dfs(i);
	}
}

int cal_buildtime(int now)
{
	if (ans[now]) return ans[now];
	int si = v[now].size();
	int maxt = 0;
	for (int i = 0; i < si; i++)
	{
		maxt = max(maxt, cal_buildtime(v[now][i]));
	}
	return maxt + buildtime[now];
}

int main()
{
	cin.tie(0); cin.sync_with_stdio(false);
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> buildtime[i];
		int a;
		while (1)
		{
			cin >> a;
			if (a == -1) break;
			v[i].push_back(a);
		}
		if (v[i].empty()) ans[i] = buildtime[i];
	}
	topological_sort();
	while(!q.empty())
	{
		int i = q.front();
		q.pop();
		ans[i] = cal_buildtime(i);
	}
	for (int i = 1; i <= N; i++)
	{
		cout << ans[i] << '\n';
	}
}



//----------------------------------------------------------------

//단순 dfs를 통해 구한 코드
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N;
int buildtime[501], ans[501], chk[501];
vector<int> pre[501];

int dfs(int now)
{
	if (ans[now]) return ans[now];
	int si = pre[now].size();
	chk[now]++;
	int maxt = 0;
	for (int i = 0; i < si; i++)
	{
		int nxt = pre[now][i];
		if (!chk[nxt]) maxt = max(maxt, dfs(nxt));
	}
	return maxt + buildtime[now];
}

int main()
{
	cin.tie(0); cin.sync_with_stdio(0);
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> buildtime[i];
		while (1)
		{
			int a; cin >> a;
			if (a == -1) break;
			pre[i].push_back(a);
		}
		if (pre[i].empty()) ans[i] = buildtime[i];
	}
	for (int i = 1; i <= N; i++)
	{
		memset(chk, 0, sizeof(chk));
		ans[i] = dfs(i);
		cout << ans[i] << '\n';
	}
}

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

문제

문제

출처

ICPC

두 코드의 결과가 다른 이유가 뭘까요?

rkdgh98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말