글 읽기 - 시간초과 해결할 방법이 없을까요?

tjrwo3080 1년 전 0

바이러스 뽑는 경우의 수 (조합 - DFS)

바이러스 퍼뜨리기 (BFS)

이렇게 구했는데 어딜 고쳐야 될까요?

비쥬얼로 돌리면 테스트케이스는 다 맞는데 시간초과가 문제네요..

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

typedef pair<int, int> p;

p virus[10];
p pp;

queue<p> que;

int N, M, answer, virus_idx, que_size, _x, _y, mv_cnt;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int arr[51][51] = { 0, };
int cpy_arr[51][51] = { 0, };
bool isSelected[10] = { 0, };

int is_full() {
	// 맵에 바이러스가 다 퍼졌는지
	int mv = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (!arr[i][j] && !cpy_arr[i][j])
				return -1;
			if (cpy_arr[i][j] > mv)
				mv = cpy_arr[i][j];
		}
	}
	return mv;
}

void move_virus() {
	// 선택된 바이러스 집어 넣기
	for (int i = 0; i < 10; i++) {
		if (isSelected[i])
			que.push(virus[i]);
	}

	// 바이러스 맵 초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cpy_arr[i][j] = 0;
		}
	}

	// 퍼뜨리기
	mv_cnt = 1;
	while (!que.empty()) {
		que_size = que.size();
		while (que_size-- > 0) {
			pp = que.front();
			que.pop();
			for (int i = 0; i < 4; i++) {
				_x = pp.first + dx[i];
				_y = pp.second + dy[i];
				if (_x <1 || _y<1 || _x > N || _y> N || (cpy_arr[_x][_y] < mv_cnt && cpy_arr[_x][_y]) || arr[_x][_y] < 0)
					continue;
				cpy_arr[_x][_y] = mv_cnt;
				que.push({ _x, _y });
			}
		}
		mv_cnt++;
	}

	// 바이러스가 다 퍼지고, 최솟값이면 대체
	mv_cnt = is_full();
	if (mv_cnt >= 0 && mv_cnt < answer) {
		answer = mv_cnt;
	}
}

void pick_virus(int idx, int cnt) {
	// 바이러스 선택 (dfs - 조합사용)
	if (cnt == M) {
		move_virus();
		return;
	}

	for (int i = idx; i < virus_idx; i++) {
		if (isSelected[i]) continue;
		isSelected[i] = 1;
		pick_virus(i, cnt + 1);
		isSelected[i] = 0;
	}
}

void solve() {
	pick_virus(0, 0);
	// 바이러스가 다 퍼진 경우가 없으면, -1
	if (answer == 101)
		answer = -1;
	cout << answer << endl;
}

void init() {
	cin >> N >> M;
	virus_idx = 0, answer = 101;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
			if (arr[i][j]) {
				if(arr[i][j] == 2) 
					virus[virus_idx++] = { i, j };
				arr[i][j] = -1;
			}
		}
	}
	solve();
}

int main(void) {
	init();
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 해결할 방법이 없을까요?

tjrwo3080 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말