[백준 14502] 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

#include <cstdio>
#include <queue>
#include <vector>

int N, M;
int map_virus[8 + 2][8 + 2];
int visited[8 + 2][8 + 2];
int choice[3 + 2];

struct _st
{
	int x; 
	int y;
};

std::queue<_st> Virus;
std::vector<_st> Blank;


int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };
int dfs_tmp;

int max_area;

void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map_virus[i][j]);
			if (map_virus[i][j] == 0) Blank.push_back({ i, j });
			else if (map_virus[i][j] == 2) Virus.push({ i, j });
		}
	}
}


void BFS(void)
{
	std::queue<_st> Q = {};
	Q = Virus;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			if (visited[nx][ny] == 1 || visited[nx][ny] == 2) continue;	// 벽이거나 이미 바이러스가 퍼진 곳이면 건너뛴다.
			visited[nx][ny] = 2;
			Q.push({ nx, ny });
		}
	}
}



void make_wall(int w1, int w2, int w3)
{
	// 벽세우기
	map_virus[Blank[w1].x][Blank[w1].y] = 1;
	map_virus[Blank[w2].x][Blank[w2].y] = 1;
	map_virus[Blank[w3].x][Blank[w3].y] = 1;
	
	// 바이러스 퍼뜨리기 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map_virus[i][j] == 1) visited[i][j] = 1;	// 벽이면 방문 배열도 1로 채워줌 
			if (map_virus[i][j] == 2) visited[i][j] = 2;	// 바이러스면 방문 배열도 2로 채워줌 
		}
	}
	BFS();

	// 원상복귀 
	map_virus[Blank[w1].x][Blank[w1].y] = 0;
	map_virus[Blank[w2].x][Blank[w2].y] = 0;
	map_virus[Blank[w3].x][Blank[w3].y] = 0;
}


int get_safe(void)
{
	int safe = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j] == 1) continue;	// 벽 건너뛴다.
			if (visited[i][j] == 2) continue;	// 바이러스 퍼진 곳 건너뛴다. 
			safe++;
		}
	}
	return safe;
}


void Combi(int n, int s)
{
	if (n == 3) {
		std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
		
		make_wall(choice[0], choice[1], choice[2]);		// 벽세우고 바이러스 퍼뜨리기
		int tmp = get_safe();							// 안전영역 구하기 
		max_area = (max_area < tmp) ? tmp : max_area;	// 안전영역 최대값 구하기 
		
		//printf("%d %d\n", tmp, max_area);
		return;
	}

	for (int i = s; i < Blank.size(); i++) {
		choice[n] = i;
		Combi(n + 1, i + 1);
	}
}



int main()
{
	input();
	Combi(0, 0);
	printf("%d\n", max_area);
	return 0;
}

원래 풀자마자 정리했어야 됐는데 미루고 미루다가 이제는 잊어버릴까봐 한다 ㅋㅋ 게으른 나자신 ㅎ...

 

문제의 조건은 간단하다. 빈칸(0)을 세 개 뽑아 벽을 세우고, 바이러스를 퍼뜨린다. 이후 안전 영역의 크기를 구하고 그 중 최대값을 도출하는 문제이다. 

 

 

// Combi( ) 함수

맵을 입력받은 후에 가장 먼저 한 일은 빈칸의 좌표들 중 벽을 세울 3개의 좌표를 뽑는 것이다. 이를 위해 DFS 함수인 Combi를 구현했다.

 

 

// make_wall( ) 함수

조합의 경우의 수가 하나씩 나올 때 마다 make_wall 함수를 통해 벽을 세웠다. 

원본인 map을 해치지 않기 위해 visited 배열을 하나 더 만들어서 바이러스이면 2, 벽이면 0을 채워주었고, 그 다음으로 바이러스를 퍼트리기 위한 BFS( ) 함수를 콜해주었다. 

바이러스 퍼트리기가 끝난 후에는 세웠던 벽을 다시 빈칸으로 바꾸어 다음 경우를 탐색하는데 영향을 미치지 않도록 하였다. 

 

 

// BFS( ) 함수

바이러스 좌표 주변의 빈 칸에 바이러스를 퍼뜨려주었다.

빠른 탐색을 위해 input 함수에서 입력받으면서 바이러스 좌표를 Virus 라는 큐에 받아주었고, 이렇게 받은 바이러스 정보들을  BFS 함수에서 사용할 임시 큐인 Q에 저장해주었다. 

 

 

// get_virus( ) 함수

이때 내가 치명적인 실수를 하나 한 것이 있다. 문제 이해를 잘못하고, 남아있는 안전 영역들 중 최대값을 구하고, 매번 벽을 다시 세워서 그것들 중의 최댓값을 다시 구해야 하는줄 알고 여기서 DFS를 한번 더 돌렸다. 

ㅋㅋㅋㅋ 당연히 타임아웃... 

그냥 남아있는 0을 세어주면 되는 문제였다. 그래서 그냥 더 생각 안하고 루프 두 번 돌려서 0의 개수를 카운팅해주었다. 

 

 

이 문제의 교훈 : 문제를 잘 읽자.. 

---

++22.11.08 갱신이지만 원래 풀었던 코드가 더 나은듯.. ? 

심지어 조합코드 실수해서 틀림.. 이런거 틀리면 이제 눈물 나는거다..

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
int R, C;
int board[8 + 2][8 + 2];

struct _st
{
	int x, y;
};
std::vector<_st> B;
std::vector<_st> V;
int B_size;
int choice[3];
int ans;

std::queue<_st> Q;
int visited[8 + 2][8 + 2];

void debug()
{
	printf("=====\n");
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%d ", board[i][j]);
		}
		printf("\n");
	}
}


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 0) B.push_back({ i, j });	// 빈칸
			else if (board[i][j] == 2) V.push_back({ i, j });	// 바이러스
		}
	}
	B_size = B.size();
}


void put_wall()
{
	for (int i = 0; i < 3; i++) {
		board[B[choice[i]].x][B[choice[i]].y] = 1;
	}
}


void spread_virus()
{
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q = {};
	memset(visited, 0, sizeof(visited));
	for (_st v : V) {
		Q.push({ v.x, v.y });
		visited[v.x][v.y] = 1;
	}

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop(); 

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 1 || board[nx][ny] == 2) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
			board[nx][ny] = 2;
		}
	}
}


int get_safe()
{
	int zeros = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 0) zeros++;
		}
	}
	return zeros;
}


void DFS(int n, int s)
{
	if (n == 3) {
		int tmp[8 + 2][8 + 2] = { 0, };
		memcpy(tmp, board, sizeof(tmp));

		put_wall();
		spread_virus();
		int area = get_safe();
		
		if (area > ans) ans = area;		
		memcpy(board, tmp, sizeof(tmp));

		return;
	}
	
	for (int i = s; i < B_size; i++) {
		choice[n] = i;
		DFS(n + 1, i + 1);
	}
}



int main()
{
	input();
	DFS(0, 0);
	printf("%d\n", ans);
	return 0;
}