글 읽기 - 시간초과 원인을 모르겠습니다

lawy3425 3년 전 0

어느부분을 줄여야 할까요...

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;


int N;
int M;//0 : 빈칸 1:벽 2 : 바이러스를 놓을수 있는 위치
int input[50][50];
int map[50][50];
bool visit[50][50];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
bool S[10];
vector<pair<int, int>> v;
int answer;
int zero;

void print()
{
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			if (input[y][x] == 1)
				cout << "- ";
			else if (input[y][x] == 2)
				cout << "* ";
			else if (map[y][x] == -1)
				cout << "_ ";
			else
				cout << map[y][x] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void virus()
{
	memset(map, -1, sizeof(map));
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			visit[y][x] = false;
		}
	}
	queue<pair<pair<int, int>, int>> q;

	int frontx;
	int fronty;
	int frontcnt;

	//선택된 바이러스
	for (int i = 0; i < 10; i++)
	{
		if (S[i] == true)
		{
			q.push({ v[i], 0 });
			visit[v[i].second][v[i].first] = true;
			map[v[i].second][v[i].first] = 0;
		}
		if (q.size() >= 3)
		{
			break;
		}
	}

	int time = 0;
	int nzero = 0;
	while (!q.empty())
	{
		frontx = q.front().first.first;
		fronty = q.front().first.second;
		frontcnt = q.front().second;
		q.pop();

		int ncnt = frontcnt + 1;
		for (int i = 0; i < 4; i++)
		{
			int nx = frontx + dx[i];
			int ny = fronty + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (input[ny][nx] == 1) continue;
			if (visit[ny][nx]) continue;

			q.push({ { nx, ny }, ncnt });
			map[ny][nx] = ncnt;
			visit[ny][nx] = true;

			if (input[ny][nx] == 0)
			{//빈칸에 바이러스 퍼뜨림
				nzero++;

				if (answer <= ncnt)
				{
					return;
				}
				else if (nzero == zero)
				{
					//모든 빈칸에 퍼뜨리고, 최소시간일 경우 갱신
					answer = ncnt;
					return;
				}
			}

		}
	}
}
void dfs(int idx, int cnt)
{
	if (cnt == M)
	{
		//print();
		virus();
		print();
		return;
	}
	for (int i = idx; i < v.size(); i++)
	{
		if (S[i] == true) continue;

		S[i] = true;
		dfs(idx, cnt + 1);
		S[i] = false;
	}
}
int main()
{
	//cin.tie(NULL);
	//cout.tie(NULL);
	//	ios::sync_with_stdio(false);
	fstream fin;
	fin.open("input.txt");

	fin >> N >> M;
	zero = 0;
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			fin >> input[y][x];
			if (input[y][x] == 2)
			{
				//바이러스를 놓을수 있는 위치
				v.push_back(make_pair(x, y));
			}
			else if (input[y][x] == 0)
			{
				zero++;
			}
		}
	}
	answer = 5000;

	if (zero == 0)
	{
		cout << "-1";
		return 0;
	}

	dfs(0, 0);

	if (answer == 5000)
	{
		answer = -1;
	}

	cout << answer;

	return 0;
}

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

문제

문제

출처

ICPC

시간초과 원인을 모르겠습니다

lawy3425 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말