글 읽기 - 로컬에서 실행 시 시간초과인데, 문제를 제출하면 정답처리 됩니다.

beomyoung93 5년 전 1

제 컴퓨터상에서 실행 시 '예제 입력 3'의 경우 실행시간이 약 17~18초가 걸립니다.

그런데 문제에서 주어진 시간 제한은 2초인데, 문제를 제출하면 정답처리가 됩니다.

원래 하려고 했던 질문은...

백트래킹으로 벽의 위치를 정하고, BFS로 안전영역의 크기를 구하는 방향으로 문제를 풀었습니다.

실행시간이 오래걸려서 어디서 조건문으로 잘 걸러내야 시간내에 처리가 가능한지 힌트 부탁드립니다.

#include<stdio.h>
#include<algorithm>
#include<queue>
#define NON 0
#define WALL 1
#define VIRUS 2
#define INFECT 3
#define SIZE 9
using namespace std;
typedef struct point {
	int row;
	int col;
}point;

int ROW, COL;
int mat[SIZE][SIZE];
queue<point> viruses;		//  2 <= 바이러스개수 <= 10	
int MAX = -1;				// 안전영역 크기의 최대값을 저장


void init() {			// 연산 중간에 'INFECT'처리된 위치만 'NON'으로 초기화하는 역할
	for (int r = 0; r < ROW; r++) {
		for (int c = 0; c < COL; c++) {
			if (mat[r][c] == INFECT) {
				mat[r][c] = NON;
			}
		}
	}
}
bool isOver(int row, int col) {		//인수로 전달 받은 위치가 경계선을 벗어났는지 검사
	if (row < 0 || ROW <= row || col < 0 || COL <= col) {
		return true;
	}
	return false;
}
void bfs() {		// 바이러스와 벽 정보를 기준으로 바이러스를 퍼뜨림.
	queue<point> q = viruses;		//main()에서 입력받은 바이러스 위치를 지역변수 queue에 저장
	point tmp;

	while (!q.empty()) {
		tmp = q.front();	q.pop();

		if (!isOver(tmp.row - 1, tmp.col) && mat[tmp.row - 1][tmp.col] == NON) {		//상단좌표 검사
			mat[tmp.row - 1][tmp.col] = INFECT;
			q.push({ tmp.row - 1, tmp.col });
		}
		if (!isOver(tmp.row + 1, tmp.col) && mat[tmp.row + 1][tmp.col] == NON) {		//하단좌표 검사
			mat[tmp.row + 1][tmp.col] = INFECT;
			q.push({ tmp.row + 1, tmp.col });
		}
		if (!isOver(tmp.row, tmp.col - 1) && mat[tmp.row][tmp.col - 1] == NON) {		//좌측좌표 검사
			mat[tmp.row][tmp.col - 1] = INFECT;
			q.push({ tmp.row, tmp.col - 1 });
		}
		if (!isOver(tmp.row, tmp.col + 1) && mat[tmp.row][tmp.col + 1] == NON) {		//우측좌표 검사
			mat[tmp.row][tmp.col + 1] = INFECT;
			q.push({ tmp.row, tmp.col + 1 });
		}
	}
}
int check() {		// 안전 영역 크기를 카운트해서 반환
	int sum = 0;

	for (int r = 0; r < ROW; r++) {
		for (int c = 0; c < COL; c++) {
			if (mat[r][c] == NON) {
				sum++;
			}
		}
	}
	return sum;
}
void backtrack(int depth) {
	if (depth == 3) {	//벽은 반드시 3개를 세워야 함 (문제에서 주어진 조건)
		bfs();
		MAX = max(MAX, check());
	}
	else {
		for (int r = 0; r < ROW; r++) {
			for (int c = 0; c < COL; c++) {
				if (mat[r][c] == NON ) {	// 해당 좌표가 'NON(=빈칸)'인 경우
					mat[r][c] = WALL;
					backtrack(depth + 1);	// 'WALL(=벽)'으로 설정 후 backtrack() 호출
					mat[r][c] = NON;		// 'WALL(=벽)'으로 설정 한 것 다시 원상복구.
					init();					// backtrack() -> bfs()에서 'INFECT'처리된 위치만 'NON'으로 원상복구
				}
			}
		}
	}
}

int main() {
	int input;

	//입력
	scanf("%d %d", &ROW, &COL);
	for (int r = 0; r < ROW; r++) {
		for (int c = 0; c < COL; c++) {
			scanf("%d", &input);
			mat[r][c] = input;
			if (input == VIRUS) {
				viruses.push({ r,c });		//바이러스의 경우 따로 저장, 이 후 bfs()에서 사용
			}
		}
	}

	//처리
	backtrack(0);

	//출력
	printf("%d\n", MAX);

	return 0;
}