글 읽기 - 17142 연구실3(삼성코딩문제) 에서 시간초과가 나는데 도와주실 수 있으신가요?

gagdusol 4년 전 1

안녕하세요, 17142 문제에 대해 질문드립니다.

제출 시, 시간초과로 나옵니다.
기본적으로 활성화 바이러스를 맵에서 정하는 것은 dfs()함수 내에서 정했고, 활성화 바이러스를 고르면, 그 값들을 -2로 바꿔줍니다. 그리고 비활성화 바이러스들은 모두 -1로 바꿔줍니다.
bfs()함수에서는 활성화바이러스들이 퍼지게 됩니다.
dfs()내부에서 bfs()를 호출하며, 큐를 이용해서 bfs()를 구현하였는데, 혹시 시간초과가 나는 의심가는 부분이 어디인지 의견을 구할 수 있을까요?

감사합니다.

#include <iostream>
#include <queue>
using namespace std;

int N;//연구소 크기
int M;//바이러스 활성화 가능 개수
int map[50][50];
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int ans;
int value_used_by_main = -1; //이 변수값이 -1이 아닌경우에만 바이러스가 퍼지는 데 걸린 시간이 출력된다.
//바이러스가 퍼진 이후, 맵에 0값이 없는 경우에만 value_used_by_main값이 0이 된다.


//비활성화 바이러스는 -1, 활성화는 -2 으로 재구성 하여 분석합니다.

void copy_from_to(int(*map)[50], int(*map_dst)[50]) {
	for (int row = 0; row < N; row++) {
		for (int col = 0; col < N; col++) {
			map_dst[row][col] = map[row][col];
		}
	}
}

bool isInside(int row, int col) {
	return (row >= 0 && row < N && col >= 0 && col < N);
}
bool noSafeZone(int(*map)[50]) {//0-> 맵에 0이 있음. 1-> 맵에 0이 없음
	for (int row = 0; row < N; row++) {
		for (int col = 0; col < N; col++) {
			if (map[row][col] == 0) return 0;
		}
	}
	return 1;
}

void bfs(int(*map)[50]) {

	int next_row, next_col;
	int next_sec;
	int cur_row, cur_col, cur_sec;
	int ans_candidate = 0;
	int sec_map[50][50] = { 0, }; //sec map_temp
	int map_temp[50][50];

	copy_from_to(map, map_temp);

	for (int row = 0; row < N; row++) {
		for (int col = 0; col < N; col++) {
			if (map_temp[row][col] == 2)
				map_temp[row][col] = -1; //비활성화 바이러스는 -1, 활성화는 -2
		}
	}



	queue <pair<int, int>> q;
	for (int row = 0; row < N; row++) {
		for (int col = 0; col < N; col++) {
			if (map_temp[row][col] == -2) 
				q.push(pair<int, int>(row, col));
		}
	}

	while (!q.empty()) {
		cur_row = q.front().first;
		cur_col = q.front().second;
		q.pop(); 

		cur_sec = sec_map[cur_row][cur_col];

		for (int i = 0; i < 4; i++) {
			next_row = cur_row + dir[i][0];
			next_col = cur_col + dir[i][1];

			if (isInside(next_row, next_col) && map_temp[next_row][next_col] == 0) {
				next_sec = cur_sec + 1;
				
				sec_map[next_row][next_col] = next_sec;
				map_temp[next_row][next_col] = -2;
				ans_candidate = max(ans_candidate, next_sec);
				q.push(pair<int, int>(next_row, next_col));
			}
		}
	}

	
	if (noSafeZone(map_temp)) { //zero값이 map_temp에 없는 경우이어야 ans를 min으로 비교해서 최신화
		ans = min(ans_candidate, ans);
		value_used_by_main = 0;

		return;
	}
	else return;

}

void dfs(int(*map)[50], int cnt) {


	if (cnt == M) {
		bfs(map);
		return;
	}
	int map_temp[50][50];
	copy_from_to(map, map_temp);

	for (int row = 0; row < N; row++) {
		for (int col = 0; col < N; col++) {
			if (map_temp[row][col] == 2) {
				map_temp[row][col] = -2;
				dfs(map_temp, cnt + 1);
				map_temp[row][col] = 2; //원상태로 복귀
			}
		}
	}

}


int main() {
	int value;
	int sec;
	ans = 2000000;


	cin >> N >> M;
	for (int row = 0; row < N; row++) {
		for (int col = 0; col < N; col++) {
			cin >> value;
			map[row][col] = value;
		}
	}
	dfs(map, 0);
	if (value_used_by_main == -1){
		ans = -1;
	}
	
	cout << ans << endl;
}

ekdya93 4년 전 0

코드를 제대로 본건 아닌데

copy_from_to 함수를 너무 많이 호출하시는거같습니다.

활성시킬 바이러스를 다 고르고 나서 bfs에 들어가기 전에 한번만 bfs용으로 map을 copy해야될거같은데

dfs를 한단계 한단계 돌때마다 copy_from_to함수가 호출되는게 일단 비효율적으로 보입니다 !

gagdusol 4년 전 0

그 copy_from_to함수를 dfs할때는 삭제해봤습니다.

그런데도 똑같이 시간초과가 나네요.. 조언 감사합니다.ㅠ 좀더 고민해보고 있는데 잘 모르겠네요

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

문제

문제

출처

ICPC

17142 연구실3(삼성코딩문제) 에서 시간초과가 나는데 도와주실 수 있으신가요?

gagdusol 4년 전 1

ekdya93 4년 전 0

gagdusol 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말