[C] Backjoon 14502 연구소

백준 14502번 문제는 연구소이다. 문제에 대한 내용과 그림 등은 백준에서 직접 확인하길 바란다. 복잡하지 않은 알고리즘 문제에서는 바로 코딩을 해도 되지만, 문제를 분석하고 어떤 함수와 요소들을 활용하여 문제를 해결할지 고민하고 정리하는 것이 시행착오를 줄일 수 있다.

문제 요구 사항을 분석하면 아래와 같다.

1. 연구소에 3개의 벽을 설치하기 위한 배열의 위치를 선정해야한다.
2. 바이러스 위치로부터 상/하/좌/우로 확산함을 나타내야하며, BFS로 구현한다.
3. 안전 영역의 크기를 계산하고 최대 값을 찾는다.

문제 상세 요건 및 분석사항은 아래와 같다.

1. 배열의 위치 선정을 위해, 가능 후보군을 입력 받을 때 모두 stack에 쌓는다.
2. 후보군 중 3개를 뽑는 조합 함수를 구성한다.
3. 여러 위치에서의 탐색을 구현하기 위해 BFS 시작 시 초기 바이러스 위치를 Queue에 올린다.

#include <stdio.h>

int map[9][9];
int c_map[9][9];
int x_stack[81];
int y_stack[81];
int x_queue[10];
int y_queue[10];
int p_wall[3];
int c_visit[81];
int b_top;
int v_front;
int front;
int rear;
int visit[9][9];
int xbfs_queue[81];
int ybfs_queue[81];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int g_max;


void init_mat(int N, int M) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			c_map[i][j] = map[i][j];
			visit[i][j] = 0;
		}
	}
}

void put_wall() {
	int idx = 0;
	for (int i = 0; i < 3; i++) {
		idx = p_wall[i];
		c_map[x_stack[idx]][y_stack[idx]] = 1;
	}	
}

void BFS(int N, int M) {
	front = rear = -1;
	while (rear < v_front) {
		rear++;
		visit[x_queue[rear]][y_queue[rear]] = 1;
		xbfs_queue[rear] = x_queue[rear];
		ybfs_queue[rear] = y_queue[rear];
	}
	while (front != rear) {
		front++;
		int x = xbfs_queue[front];
		int y = ybfs_queue[front];
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= N || ny >= M || nx < 0 || ny < 0) continue;
			if (visit[nx][ny] == 1 || c_map[nx][ny] == 1) continue;
			visit[nx][ny] = 1;
			c_map[nx][ny] = 2;
			rear++;
			xbfs_queue[rear] = nx;
			ybfs_queue[rear] = ny;
		}
	}
	for (int i = 0; i <= rear; i++) {
		xbfs_queue[i] = 0;
		ybfs_queue[i] = 0;
	}
}

int safe_count(int N, int M) {
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (c_map[i][j] == 0) count++;
		}
	}
	return count;
}

void combi(int n, int v, int N, int M) {	
	if (n == 3) {
		init_mat(N, M);
		put_wall();
		BFS(N,M);
		int max = safe_count(N,M);
		if (g_max < max) g_max = max;
	}
	else {
		for (int i = v; i <= b_top; i++) {
			if (c_visit[i] == 1) continue;
			c_visit[i] = 1;
			p_wall[n] = i;
			combi(n + 1, i,N, M);
			c_visit[i] = 0;
			p_wall[n] = 0;
		}
	}
}

int main() {
	int N, M;
	int temp = 0;
	scanf("%d %d", &N, &M);
	b_top = v_front = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &temp);
			map[i][j] = temp;
			if (temp == 0) {
				++b_top;
				x_stack[b_top] = i;
				y_stack[b_top] = j;
			}
			else if (temp == 2) {
				++v_front;
				x_queue[v_front] = i;
				y_queue[v_front] = j;
			}
		}
	}

	combi(0, 0, N, M);
	printf("%d", g_max);
	return 0;
}