글 읽기 - 시간 초과에 대해 조언해주실분!

wferel 4년 전 0

코드에 주석 달아놨습니다.

저의 접근 방법은 dfs로 조합하여 확산속도를 계산하여 최솟값을 갱신합니다.

만약 확산속도를 계산 중에 최솟값이 넘어가면 더 계산을 하지 않고 끝냅니다.

밑의 코드에서 어떠한 문제점이 있을까요?? 계산이 비효율적인지, dfs가 비효율적인지 궁금합니다

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>

using namespace std;
pair<int, int> virus[11];
int vIdx = 0;
int tmpMap[51][51];
int map[51][51];
int checked[51][51];
int tmpChe[51][51];
int dirX[4] = { -1,0,1,0 };
int dirY[4] = { 0,1,0,-1 };
int minNum = 987654;
int n, m;

int calculate_spread() //맵이 바이러스로 꽉 찼는지 계산
{
	int cnt=0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (tmpMap[i][j] == 0)
				cnt++;

	return cnt;
}

int check_map() // if(퍼지기 전 바이러스 총합 == 후 바이러스 총합) ==> 끝
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			sum += tmpMap[i][j];
	return sum;
}

int calculate_second()
{
	int prev, next;
	int num = 2;
	int cnt = 0;
	int i, j, k, nx, ny;
	bool run = true;
	prev = check_map(); //퍼지기 전 바이러스 총합
	while (run)
	{
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				if (tmpMap[i][j] == num && tmpChe[i][j] == 1)
					for (k = 0; k < 4; k++)
					{
						nx = i + dirX[k]; ny = j + dirY[k];
						if (nx > 0 && nx <= n && ny > 0 && ny <= n && (tmpMap[nx][ny] == 0 || tmpMap[nx][ny]==2) && tmpChe[nx][ny]!=1)
						{
							tmpMap[nx][ny] = num + 1;
							tmpChe[nx][ny] = 1;
						}
					}
			}
		}
		next = check_map(); //퍼진 후 바이러스 총합
		if (prev == next) //전과 후의 총합이 같은 경우
		{
			run = 0; cnt = 123456;
		}
		else if (calculate_spread() == 0)//바이러스 확산이 끝난 경우
			run = 0;
		else if (cnt > minNum) //이전 경우의 확산 속도보다 지금 속도가 더 커지면 계산을 더 하지 않고 끝냄
			run = 0;
		prev = next;
		num++;
		cnt++;
	}
	return cnt;
}

void dfs(int count, int index)
{
	if (count == m)
	{
		memcpy(tmpMap, map, sizeof(map));
		memcpy(tmpChe, checked, sizeof(checked));
		int num = calculate_second();
		if (num < minNum)
			minNum = num;
	}
	for (int i = index; i < vIdx; i++)
	{
		checked[virus[i].first][virus[i].second] = 1;
		dfs(count + 1, i + 1);
		checked[virus[i].first][virus[i].second] = 0;
	}
}

int main()
{
	int cnt=0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 2)
			{
				virus[vIdx].first = i;
				virus[vIdx].second = j;
				vIdx++;
			}
			else if (map[i][j] == 0)
				cnt++;
		}
	}
	
	if (cnt == 0)
		minNum = 0;
	else
		dfs(0, 0);
	
	if (minNum == 123457)
		minNum = -1;
	cout << minNum;
	return 0;
}

poiu090 3년 전 1

calculate_second() 에서 while(run)가 worst case에서 대단히 많은 시간복잡도를 가져요

N = 50 일때 50 * 50 * 4 * (while문 반복 수) 최소 1만번인데 조합의 각 경우마다 이만큼 돈다면 시간초과가 나겠죠?

각 좌표를 돌면서 주변으로 확산시키는 것보다 이미 바이러스가 퍼진 좌표를 기준으로 확산시키세요

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

문제

문제

출처

ICPC

시간 초과에 대해 조언해주실분!

wferel 4년 전 0

poiu090 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말