글 읽기 - 문제의 반례를 못찼겠습니다ㅠㅠ

lawliet777 4년 전 0

고민해봐도 어렵네요...혹시 도움을 주신다면 감사하겠습니다(__)

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include<algorithm>
#include <memory.h>
//#include<functional>
//#include<stdio.h>
//#include<cstdio>
//#include<cmath>
using namespace std;

typedef long long LL;
typedef long long int LLI;
typedef long L;
#define MIN(a,b) a>b ? b:a;
#define MAX(a,b) a<b ? b:a;

const int oo = 0x3f3f3f3f;

//https://www.acmicpc.net/problem/14502
//연구소 문제
//문제 : N*M크기의 연구소에 바이러스 2가 침투(ㅡㅡ2진법ㅋㅋ)
//		0과1(벽)과2의 위치가 주어진 연구소에서, 1을 3개만 더 추가하자.
//		이 때 나올 수 있는 안전지역의 최대 갯수?
//동치 : 결국, 벽의 위치 3개를 고를 수 있는 모든 경우의 수를 다 따진 후에
//		거기서 바이러스를 spard시켜서, 안전지역의 수를 검사하면 됨.
//		(왜냐하면 연구소크기가 8^2이니까, 0의 갯수 중 nCr을 통해 3개를 뽑아
//		1로 바꾸는 경우의 수는 64C3이고, 여기에 * spard는 64개 검사 < 2초
//조건 : 벽을 만나면 바이러스가 퍼질 수 없다. 한편 spard에는 BFS를 이용
struct virusP {
	int x;
	int y;
	virusP() {};
	virusP(int x, int y) {
		this->x = x;
		this->y = y;
	}
};

int N, M;
int ans=-oo;

int Lab[10][10];

int virus_num = 0;
virusP backup_virus_point[12];
queue<virusP> virus_point;

void print_Lab() {
	for (int i = 0; i <= N + 1;i++) {
		for (int j = 0;j <= M + 1;j++) {
			cout << Lab[i][j] << " ";
		}
		cout << endl;
	}
}

void sprad_bfs() {
	int dx[5] = { 0,-1,+1,0,0 };
	int dy[5] = { 0,0,0,-1,+1 };

	while (!virus_point.empty()) {
		virusP cur = virus_point.front();
		virus_point.pop();
		int x = cur.x;
		int y = cur.y;

		//상 하 좌 우에 전달하고, 그걸 큐에 넣기
		for (int dir = 1;dir <= 4;dir++) {
			int next_x = x + dx[dir];
			int next_y = y + dy[dir];

			if (Lab[next_x][next_y] == 0) {
				Lab[next_x][next_y] = 2;
				virus_point.push(virusP(next_x, next_y));
			}
		}
	}

	//복구 시켜주기(dfs안에 들어가기 때문)
	for (int i = 1; i <= virus_num;i++) {
		virus_point.push(backup_virus_point[i]);
	}
}

int find_safe() {
	int rt = 0;
	for (int i = 1; i <= N;i++) {
		for (int j = 1; j <= M;j++) {
			if (Lab[i][j] == 0) {
				rt++;
			}
		}
	}
	
	return rt;
}

void dfs(int nCr, int count) {
	int backup_Lab[10][10] = { 0 };

	if (count == 3) {
		memcpy(backup_Lab, Lab, sizeof(Lab));

		sprad_bfs();
//		print_Lab();
		int candi=find_safe();
		ans = MAX(ans, candi);

		//다 끝났으면, 바이러스 퍼진 Lab를 다시 복구 시켜주기
		memcpy(Lab, backup_Lab, sizeof(backup_Lab));
		return;
	}

	//조합으로 받아야 함으로 dfs인자에 int nCr추가하기
	for (int i = nCr; i <= N*M;i++) {
		int x = (i / M) + 1; 
		int y = i % M; if (y == 0) y = M;
		
		if (Lab[x][y] != 0) continue;

		Lab[x][y] = 1;
		dfs(i + 1, count + 1);
		Lab[x][y] = 0;
	}

}

int main() {
	cin >> N >> M;

	for (int i = 1; i <= N;i++) {
		for (int j = 1; j <= M;j++) {
			cin >> Lab[i][j];
			if (Lab[i][j] == 2) {
				virus_num++;
				backup_virus_point[virus_num] = virusP(i, j);	
				virus_point.push(virusP(i, j));
			}

			//벽을 새워서 편하게 풀기
			Lab[0][j] = 1;
			Lab[N + 1][j] = 1;
			Lab[i][0] = 1;
			Lab[i][M + 1] = 1;
		}
	}

//	print_Lab();

	int count = 0;
	int nCr = 1;
	dfs(nCr, count);

	cout << ans;
}

nahwasa 4년 전 1

반례입니다.

답 : 0
출력 : -1061109567

lawliet777 4년 전 1

감사합니다. 해결하였습니다.

i%M과 i/M부분에서 i가 M의 배수일 때 y 뿐만 아니라 x도 조정을 해줘야 하네요ㅎㅎ 감사합니다.

nahwasa 4년 전 1

저도 재밌는 문제 만나게 해주셔서 감사합니다. ( _ _)

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

문제

문제

출처

ICPC

문제의 반례를 못찼겠습니다ㅠㅠ

lawliet777 4년 전 0

nahwasa 4년 전 1

lawliet777 4년 전 1

nahwasa 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말