글 읽기 - 시간 초과가 나는 코드입니다.

sejungpk 5년 전 0

N일부터 시작
[N+1][떡 종류]로 방문 처리
N == 0이면 바로 출력 후 빠져 나올 수 있도록 flag 처리

어디 부분에서 시간 초과가 나는 걸까요?

#include<iostream>
#include<vector>

using namespace std;

int N;
vector<int> v[1001];
bool visit[1001][10];
vector<int> tmp;
bool flag = false;
void Dfs(int day) 
{
	if (flag)
		return;

	if (day == 0)
	{
		int size = tmp.size();
		for (int i = 0; i < size; i++)
			cout << tmp[i] << "\n";

		flag = true;
		return;
	}

	int size = v[day].size();
	for (int i = 0; i < size; i++)
	{
		if (!visit[day+1][v[day][i]])
		{
			visit[day][v[day][i]] = true;
			tmp.push_back(v[day][i]);
			Dfs(day-1);
			tmp.pop_back();

			if (flag)
				return;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;

	for (int n = 1; n <= N; n++)
	{
		int cnt;
		cin >> cnt;

		for (int i = 0; i < cnt; i++)
		{
			int num;
			cin >> num;
			v[n].push_back(num);
		}
	}

	Dfs(N);

	if (!flag)
		cout << -1 << "\n";
		

	return 0;
}

djm03178 5년 전 0

이 부분이 이상합니다. 하나는 day+1이고 하나는 day네요.

		if (!visit[day+1][v[day][i]])
		{
			visit[day][v[day][i]] = true;

sejungpk 5년 전 0

아 저는 day + 1의 v[day][i] 떡이 방문처리 되어 있지 않으면 day에 v[day][i]를 방문 처리 해줬습니다.

이런 식으로 로직을 짜면 안되나요?

djm03178 5년 전 0

그렇게 하면 이런 경우 매우 오랜 시간이 걸리게 됩니다.

sejungpk 5년 전 0

말씀을 보고 코드를 수정해봤습니다.

전날 떡과 다른 경우와 당일날 떡이 방문처리가 되어 있지 않으면

방문처리 후 dfs를 돌렸는데 이번에는 틀렸다고 나오는군요 ㅠㅠㅠㅠ

#include<iostream>
#include<vector>

using namespace std;

int N;
vector<int> v[1010];
bool visit[1010][11];
vector<int> tmp;
bool flag = false;
void Dfs(int day, int dduk) 
{
	if (flag)
		return;

	if (day == N + 1)
	{
		int size = tmp.size();
		for (int i = 0; i < size; i++)
			cout << tmp[i] << "\n";

		flag = true;
		return;
	}

	int size = v[day].size();
	for (int i = 0; i < size; i++)
	{
		if (v[day][i] != dduk && !visit[day][v[day][i]])
		{
			visit[day][v[day][i]] = true;
			tmp.push_back(v[day][i]);
			Dfs(day+1, v[day][i]);

			if (flag)
				return;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;

	for (int n = 1; n <= N; n++)
	{
		int cnt;
		cin >> cnt;

		for (int i = 0; i < cnt; i++)
		{
			int num;
			cin >> num;
			v[n].push_back(num);
		}
	}

	Dfs(1, 0);

	if (!flag)
		cout << -1 << "\n";
		

	return 0;
}

djm03178 5년 전 0

답을 찾지 못했을 때 pop_back을 하는 부분이 없네요.

sejungpk 5년 전 0

해결했습니다 정말 감사합니다

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

문제

문제

출처

ICPC

시간 초과가 나는 코드입니다.

sejungpk 5년 전 0

djm03178 5년 전 0

sejungpk 5년 전 0

djm03178 5년 전 0

sejungpk 5년 전 0

djm03178 5년 전 0

sejungpk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말