글 읽기 - 16432 무엇이 틀렸는지는 알겠는데 해결을 어떻게 해야할 지 고민입니다

dnjs2113 5년 전 0

3 1 2 3

2 1 2

1 2

와 같은 경우에 저는 앞에서부터 dfs를 수행하여 처음에 1을 넣고 그 다음줄은 1을 제외한 2를 넣어서 마지막에는 2밖에 없어서 1을 출력합니다.

이 부분을 어떻게 해결해야할 지 모르겠어서 첫 질문드립니다!

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

int check[1001] = { 0, };
int temp_c = 0;

void dfs(int arr[][10], int k, int che);

int main(void)
{
	int cake[1001][10] = { 0, };
	int N, temp,num, i, j;

	//input
	scanf("%d", &N);

	//error check
	if (N < 1 || N>1000)
		return 0;

	for (i = 0; i < N; i++)
	{
		scanf("%d", &temp);

		if (temp < 1 || temp>9)
			return 0;

		for (j = 0; j < temp; j++)
		{
			scanf("%d", &num);
			if (num < 1 || num>9)
				return 0;

			cake[i][num]++;
		}
	}

	//첫째날부터 dfs수행
	dfs(cake, 0, 0);

	if (temp_c < N)
	{
		printf("-1");
		return 0;
	}
	else
	{
		for (i = 1; i <= temp_c; i++)
			printf("%d\n", check[i]);
	}

	return 0;
}

void dfs(int arr[][10], int k, int che)
{
	int i;

	for (i = 1; i <= 9; i++)
	{
		if (arr[k][i] != 0)
		{
			if (i != che)
			{
				arr[k][i]--;
				check[++temp_c] = i;
				dfs(arr, k + 1, i);
				break;
			}
			else
			{
				continue;
			}
		}
	}
}

djm03178 5년 전 1

중간에 더 진행할 수 없는 상황이 나오면 뒤로 돌아가서 다른 걸 시도해보아야 합니다. 무조건 모든 경우의 수를 돌리면 시간 초과가 나니 방문 체크도 잘 해야 합니다.

dnjs2113 5년 전 0

네 그부분을 어떻게 해결해야할 지 고민입니다 ㅠ

답변감사합니다!

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

문제

문제

출처

ICPC

16432 무엇이 틀렸는지는 알겠는데 해결을 어떻게 해야할 지 고민입니다

dnjs2113 5년 전 0

djm03178 5년 전 1

dnjs2113 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말