글 읽기 - 시간초과 질문있습니다(코드첨부)

hhs250 5년 전 0

어디서 시간초과가 나는걸까요..? ㅠㅠㅠ

정답이 틀려서 시간초과가 나는 경우도 있나요?

리뷰 부탁드립니다... 감사합니다

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int n, m, chicken_cnt = 0, house_cnt = 0;
int map[52][52] = { 0 };
int c_y[52] = { 0 }, c_x[52] = { 0 }; // 치킨 집 y좌표 x좌표
int h_y[52] = { 0 }, h_x[52] = { 0 }; // 집 y좌표 x좌표
int minn=999999 , temp_min;
bool visited[52] = { 0 }; // 치킨 집 방문여부
void dfs(int y, int x, int cnt)
{
	int temp, sum=0;

	if (cnt > house_cnt)
		return;
    // cnt==m일 경우 집마다 치킨거리 최소값 찾기
	if (cnt == m)
	{
		for (int i = 0; i < house_cnt; i++)
		{
			temp_min = 999999;
			for(int j=0;j<chicken_cnt;j++)
			{
				if(visited[j] == true)
				{
					temp = abs(h_y[i] - c_y[j]) + abs(h_x[i] - c_x[j]);
					temp_min = min(temp_min, temp);
				}					
			}
			sum += temp_min;
		}
		minn = min(minn, sum);
		return;
	}
	for (int i = cnt; i < chicken_cnt; i++)
	{
			if(!visited[i])
			{
				visited[i] = true;
				dfs(c_y[i], c_x[i], cnt + 1);
				visited[i] = false;
			}
				
	}
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2)
			{
				c_y[chicken_cnt] = i;
				c_x[chicken_cnt++] = j;
			}
			else if (map[i][j] == 1)
			{
				h_y[house_cnt] = i;
				h_x[house_cnt++] = j;
			}
		}
	}
	for (int i = 0; i < chicken_cnt; i++)
	{
		visited[i] = true;
		dfs(c_y[i], c_x[i], 1);
		visited[i] = false;
	}
	printf("%d", minn);

	return 0;
}

djm03178 5년 전 1

정답이 틀리면 무조건 "틀렸습니다" 입니다. 시간 초과는 프로그램이 제한 시간 내에 끝이 안 나야 받습니다.

djm03178 5년 전 1

틀린 곳들을 잡아보면 다음과 같습니다.

치킨집을 어떤 순서로 고르느냐는 상관이 없으므로, 항상 앞에서 뒤로만 골라도 됩니다. 그런데 cnt는 지금까지 치킨집을 몇 개 골랐느냐이지, 지금까지 확인한 치킨집이 몇 개인지를 뜻하지는 않습니다. 그래서 뒤쪽을 고른 뒤에 다시 앞쪽을 고르는 일이 발생하고, 이게 시간복잡도를 매우 높이게 됩니다. 시간 초과의 원인은 이것입니다. 지금까지 확인한 치킨집이 몇 개인지를 함께 인자로 넘기고, 36번째 줄의 for문도 그에 맞추어서 돌리면 됩니다.
15번째 줄은 이상한 조건입니다. 치킨집을 골라서 서로 별개의 집에 대응시키는 것이 아니라, 그냥 제일 가까운 집이라면 중복될 수도 있는 거기 때문에 이런 조건을 껴넣으면 안 됩니다.
집의 수는 2N개를 넘지 않는다고 했습니다. 따라서 h_y, h_x의 크기도 최소 100이 되어야 합니다.

hhs250 5년 전 0

다시 한 번 풀어보겠습니다.

답변 감사합니다.

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