글 읽기 - 14502번 시간초과 질문드립니다. ㅠㅠ

myabc17 4년 전 0

47%에서 시간초과가 뜨는데 예시1번도 빠르게 되지않긴 합니다. ㅠㅠㅠ

어디를 고쳐야할까요?

다른분들은 DFS로 벽을 세우던데 저렇게 하는것과 똑같지 않나요?

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<vector<int>> map(8, vector<int>(8, 0));
vector<pair<int, int>> zero;
vector<pair<int, int>> virus;

int dir_x[4] = { 1,0, -1,0 };
int dir_y[4] = { 0,1,0,-1 };
int visit[8][8] = { 0 };
int N, M;

void init_visit(vector<vector<int>> copy_map) {
	for (int i = 0; i < copy_map.size(); i++) {
		for (int j = 0; j < copy_map[i].size(); j++) {
			if (copy_map[i][j] == 0)
				visit[i][j] = 0;
			else
				visit[i][j] = 1;
		}
	}
}
bool isRange(vector<vector<int>> copy_map, int row, int col) {
	if (row < 0 || row >= N || col < 0 || col >= M)
		return false;
	return true;
}

// 3. '0'의 개수 세기
int zero_count(vector<vector<int>> copy_map) {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (copy_map[i][j] == 0)
				cnt++;
		}
	}
	return cnt;
}
// 2. bfs로 바이러스 퍼뜨리기
int bfs(vector<vector<int>> copy_map) {
	queue<pair<int, int>> q;
	init_visit(copy_map);

	for (int i = 0; i < virus.size(); i++)
		q.push(virus[i]);

	while (!q.empty()) {
		pair<int, int> virus_positon = q.front();
		q.pop();
		int row = virus_positon.first;
		int col = virus_positon.second;

		for (int i = 0; i < 4; i++) {
			int new_row = row + dir_y[i];
			int new_col = col + dir_x[i];
			if (!isRange(copy_map, new_row, new_col)) // 범위체크
				continue;
			if (copy_map[new_row][new_col] == 0 && visit[new_row][new_col] == 0) {
				q.push(make_pair(new_row, new_col));
				visit[new_row][new_col] = 1;
				copy_map[new_row][new_col] = 2;
			}
		}
	}
	return zero_count(copy_map);
}

// 1. 벽세우기 ('zero' 배열은 '0'의 위치를 모아놓은 배열)
int solution(int row, int col) {
	int size = zero.size(), answer = 0;
	for (int i = 0; i < size - 2; i++) {
		for (int j = i + 1; j < size - 1; j++) {
			for (int k = j + 1; k < size; k++) {
				// map 복사
				vector<vector<int>> copy_map;
				copy_map.assign(map.begin(), map.end());

				pair<int, int> first, second, third;
				first = zero[i];
				second = zero[j];
				third = zero[k];
				copy_map[first.first][first.second] = 1;
				copy_map[second.first][second.second] = 1;
				copy_map[third.first][third.second] = 1;

				int result = bfs(copy_map); // 벽을 세운 다음 map에서 virus 퍼뜨리기
				answer = answer > result ? answer : result; // 기존 값과 비교해서 크면 갱신
			}
		}
	}
	return answer;
}
int main() {
	int answer = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				zero.push_back(make_pair(i, j));
			if (map[i][j] == 2)
				virus.push_back(make_pair(i, j));
		}
	}
	printf("%d\n", solution(N, M));
}

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

문제

문제

출처

ICPC

14502번 시간초과 질문드립니다. ㅠㅠ

myabc17 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말