글 읽기 - 반례 찾습니다.

lonecitizen 4년 전 0

우선 next_permutation으로 조합사용해서 활성바이러스 선별했습니다!

선별후 BFS 이용해서 map[][]에서 1씩 증가시켜가며 max를 찾았구요.

모든 활성/비활성 바이러스 자리는 0으로 만들고 탐색했으며, 이렇게 할 시에 발생하는 문제중에,

마지막으로 활성화되는 칸들이 빈칸이었던 칸이 전혀 없이 모두 비활성 바이러스 일 경우에 불필요하게 1초가 더 카운트되는 문제가 있을 것으로 예상했습니다. 그래서 maxviruscount와 maxcount를 두어 최대소요시간에 방문하는 모든 인덱스가 비활성 바이러스가 존재하는 인덱스인지 확인하고, 조건 만족시 max를 1 낮추는 방식으로 답을 구해보려했습니다.

여러분들이 올려주신 반례도 다 통과하는 것 같고 테스트케이스도 모두 만족하는데, 어느 부분이 잘못된 것인지 궁금합니다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int map[51][51], N, M, virus = 0, ans = 2e9, emptySpace = 0, dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pair<int, int>> virus_cord;

void BFS(vector<int> p) {
	int temp[51][51], max = 0, count = -virus;
	queue<pair<int, int>> q;
	
	for (int row = 1; row <= N; row++) {
		for (int col = 1; col <= N; col++) {
			temp[row][col] = map[row][col];
		}
	}
	for (int i = 0; i < p.size(); i++) {
		if (p[i] == 1) {
			q.push(virus_cord[i]);
		}
		int row = virus_cord[i].first;
		int col = virus_cord[i].second;
		temp[row][col] = 0;
	}

	while (!q.empty()) {
		int row = q.front().first;
		int col = q.front().second;

		q.pop();

		for (int d = 0; d < 4; d++) {
			int nrow = row + dir[d][0];
			int ncol = col + dir[d][1];

			if (nrow < 1 || ncol < 1 || nrow > N || ncol > N) continue;
			if (temp[nrow][ncol] != 0) continue;
			count++;
			temp[nrow][ncol] = temp[row][col] + 1;

			if (temp[nrow][ncol] > max) max = temp[nrow][ncol];
			q.push(make_pair(nrow, ncol));
		}
	}

	int maxviruscount = 0;
	int maxcount = 0;

	for (int row = 1; row <= N; row++) {
		for (int col = 1; col <= N; col++) {
			if (temp[row][col] == max) {
				maxcount++;
				for (int i = 0; i < virus_cord.size(); i++)
				{
					int nrow = virus_cord[i].first;
					int ncol = virus_cord[i].second;
					if (nrow == row && ncol == col) maxviruscount++;
				}
			}
		}
	}

	if (maxviruscount == maxcount) 
		max--;
	if (count == emptySpace && max < ans) ans = max;
}
int main()
{
	cin >> N >> M;
	for (int row = 1; row <= N; row++) {
		for (int col = 1; col <= N; col++) {
			cin >> map[row][col];
			if (map[row][col] == 2) {
				virus_cord.push_back(make_pair(row, col));
				virus++;
			}
			else if (map[row][col] == 0) emptySpace++;
		}
	}

	vector<int> permute;
	for (int i = M; i < virus_cord.size(); i++) permute.push_back(0);
	for (int i = 0; i < M; i++) permute.push_back(1);
	
	BFS(permute);
	while (next_permutation(permute.begin(), permute.end())) {
		BFS(permute);
	}
	if (emptySpace == 0) ans = 0;
	else if (ans == 2e9) ans = -1;
	cout << ans;
}

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

문제

문제

출처

ICPC

반례 찾습니다.

lonecitizen 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말