글 읽기 - 아무리줄여도 시간초과가 나요!!

wjavm2 4년 전 0

코드를 아무리줄여도 시간초과가 나는데.. 가지치기 하는방법 아시는분 도움좀 부탁드립니다ㅠㅠ

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

struct info { int x, y; };
int N, M;
int MMin = 99999999;
int emptyroom = 0;
int Lab[55][55];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<info>Virus;
info selecVirus[55];

void spreadV();
void Selectvirus(int cnt);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> Lab[i][j];
			if (Lab[i][j] == 2)
			{
				Virus.push_back({ i,j });
			}
			else if (Lab[i][j] == 0)
				emptyroom++;

		}
	}

	if (emptyroom == 0) cout << 0 << "\n";

	else
	{
		Selectvirus(0);
		if (MMin == 99999999) cout << -1 << "\n";
		else cout << MMin << "\n";
	}
	
	return 0;
}

void Selectvirus(int cnt)
{
	if (cnt == M)
	{
		spreadV();
		return;
	}

	for (int i = cnt; i < Virus.size(); i++)
	{
		selecVirus[cnt]={ Virus[i].x,Virus[i].y };
		Selectvirus(cnt + 1);
	}
}

void spreadV()
{
	int emptycnt = emptyroom;
	int maxt = 0;
	queue<pair<info, int>>Q;
	bool check[55][55] = { false };

	for (int i = 0; i < M; i++)
	{
		check[selecVirus[i].x][selecVirus[i].y] = true;
		Q.push({ {selecVirus[i].x,selecVirus[i].y},0 });
	}

	while (!Q.empty())
	{
		int cx = Q.front().first.x;
		int cy = Q.front().first.y;
		int time = Q.front().second;
		Q.pop();

		maxt = max(maxt, time); //시간계속 최댓값으로 업데이트

		for (int i = 0; i < 4; i++)
		{
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
			if (check[nx][ny] == false)
			{
				if (Lab[nx][ny] == 0)
				{
					check[nx][ny] = true;
					Q.push({ {nx,ny},time + 1 });
					emptycnt--;
					continue;
				}

				else if (Lab[nx][ny] == 2)
				{
					check[nx][ny] = true;
					Q.push({ {nx,ny},time + 1 });
					continue;
				}
			}
			if (emptycnt == 0) break;
		}

		if (emptycnt == 0)
		{
			maxt = max(maxt, time + 1);
			MMin = min(MMin, maxt);
			break;
		}
	}

}

babo751 4년 전 0

해결 하셨나요???

활성화 바이러스를 선택하는 코드에서 cnt, i 두개를 가지고 조절하지 않습니까???

거기서 dfs가 돌고 cnt가 작아져 중복이 발생하네요

print 찍은거

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2
0 0
1 5
4 3
6 0
6 6

0 0
1 5
4 3

0 0
1 5
6 0

0 0
1 5
6 6

0 0
4 3 <= 중복
4 3

0 0
4 3
6 0

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

문제

문제

출처

ICPC

아무리줄여도 시간초과가 나요!!

wjavm2 4년 전 0

babo751 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말