글 읽기 - 17142 연구소 3 시간초과 관련 질문입니다.

gustjr1259 4년 전 0

시간초과가 계속 발생해서 다른분들 코드도 참고해서 수정해봤는데 계속 시간초과가 납니다.

M개를 조합으로 뽑고 bfs를 하는 부분은 동일한 것 같은데 어느 부분에서 시간초과가 나는지 모르겠습니다.

알려주시면 감사하겠습니다!!

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;


int N, M;
int map[50][50];
int visit[50][50];
vector<pair<int, int>> virus;
int visited[10];
int dx[] = { 0,1,0,-1 };
int dy[] = { -1,0,1,0 };
int answer = 10000000;
int empty_place;
void dfs(int index, int cnt)
{
	if (cnt == M)
	{
		//뽑은 바이러스에 대해 bfs 수행
		queue<pair<int, int>> q;
		//visit 초기화
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				visit[i][j] = 0;
			}
		}
		for (int i = 0; i < virus.size(); i++)
		{
			//뽑힌바이러스를 큐에넣어줌
			if (visited[i] == 1)
			{
				q.push(make_pair(virus[i].first,virus[i].second));
				visit[virus[i].first][virus[i].second] = 1;
			}
		}
		int infect = 0;
		int total = 0;
		//bfs수행
		while (!q.empty())
		{
			pair<int, int> cur = q.front(); q.pop();
			
			//이동
			int nx, ny;
			for (int i = 0; i < 4; i++)
			{
				nx = cur.second + dx[i];
				ny = cur.first + dy[i];
				
				//경계,visit
				if (nx<0 || ny<0 || nx>N - 1 || ny>N - 1||visit[ny][nx]!=0)
					continue;
				
				//벽이거나 바이러스면
				if (map[ny][nx]==1||map[ny][nx]==2)
					continue;

				infect++;
				visit[ny][nx] = visit[cur.first][cur.second] + 1;
				total = visit[ny][nx];
				q.push({ ny,nx });
			}
		}

		if (infect == empty_place)
			answer = min(answer, total);
		return;
	}
	for (int i = index; i < virus.size(); i++)
	{
		if (visited[i] == 0)
		{
			visited[i] = 1;
			dfs(index + 1, cnt + 1);
			visited[i] = 0;
		}
	}
	
}
int main()   
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(0);
	cin >> N >> M;
	//맵 채우기 0:빈칸 1:벽 2: 바이러스
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
			//빈공간이면
			if (map[i][j] == 0) empty_place++;
			//바이러스면
			else if (map[i][j] == 2)
				virus.push_back({ i,j });
		}
	}
	
	//바이러스 M개 뽑기
	dfs(0, 0);
	

	if (answer == 10000000)
		cout << -1 << '\n';
	else if (answer == 0)
		cout << 0 << '\n';
	else
		cout << answer - 1 << '\n';
}

rhdqor213 4년 전 0

78번째 줄 for 문의 조건문을 잘 생각해보세요. i가 virus.size()까지 돌지 않아도 됩니다.

또한 이 반례를 생각해보세요. https://www.acmicpc.net/board/view/36342

robin00q 4년 전 0

74~76번째 줄을 while문 안에서 사용한다면 조금 더 효율을 높일 수 있을 것 같아요

또한 while문 안에서 현재 if(answer <= total) 인 경우 바로 bfs를 종료해서 pruning을 한다면 좋을 것같아요

그리고

64, 65번째 줄에서

if (map[ny][nx]==1||map[ny][nx]==2)
continue;

로 하셨는데

문제를 읽어보면 활성 바이러스가 비활성 바이러스를 만난 경우 비활성바이러스를 활성으로 바꾸라는 부분이 있어서 틀리신 것일 수도 있을 것 같네요

문제를 한번 더 자세히 읽어보시면 좋을 것 같아요

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

문제

문제

출처

ICPC

17142 연구소 3 시간초과 관련 질문입니다.

gustjr1259 4년 전 0

rhdqor213 4년 전 0

robin00q 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말