[백준#C++] 연구소

문제

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

접근 과정

1. BFS를 통해 벽 위치를 고려

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int Y, X, a[11][11], bfs_a[11][11], cnt, maxcnt;
bool check[11][11], bfs_check[11][11];
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };
vector<pair<int, int>> ans;

void input() {
	scanf("%d%d",&Y,&X);
	for (int i = 1; i <= Y; i++) {
		for (int j = 1; j <= X; j++) {
			scanf("%d",&a[i][j]);
			bfs_a[i][j] = a[i][j];
		}
	}
}

void bfs(int y, int x) {
	queue<pair<int, int>> q;

	for (int i = 1; i <= Y; i++) {
		for (int j = 1; j <= X; j++) {
			if (bfs_a[i][j] == 2) {
				q.push(make_pair(i, j));
				bfs_check[i][j] = true;
			}
		}
	}
	
	while (!q.empty()) {
		int iy, ix;
		iy = q.front().first;
		ix = q.front().second;
		q.pop();

		//남 북 동 서 순
		for (int k = 0; k < 4; k++) {
			int ny, nx;
			ny = iy + dy[k];
			nx = ix + dx[k];

			if (ny >= 1 && nx >= 1 && ny <= Y && nx <= X) {
				if (bfs_a[ny][nx] == 0) {
					if (bfs_check[ny][nx]) continue;

					bfs_check[ny][nx] = true;
					q.push(make_pair(ny, nx));
					bfs_a[ny][nx] = 2;
				}
			}
		}
	}

}

void copy() {
	for (int i = 1; i <= Y; i++) {
		for (int j = 1; j <= X; j++) {
			bfs_a[i][j] = a[i][j];
		}
	}
}

void cnt_cal() {
	for (int i = 1; i <= Y; i++) {
		for (int j = 1; j <= X; j++) {
			if (bfs_a[i][j] == 0) cnt++;
		}
	}

}

void go(int y,int x) {

	if (ans.size() == 3) {
		cnt = 0;
		for (int i = 0; i < 3; i++) {
			a[ans[i].first][ans[i].second] = 1;
		}
        
		copy();
		
		bfs(1,1);

		memset(bfs_check, false, sizeof(bfs_check));

		cnt_cal();

		if (maxcnt < cnt) maxcnt = cnt;

		for (int i = 0; i < 3; i++) {
			a[ans[i].first][ans[i].second] = 0;
		}

		copy();
		return;
	}

	for (int i = 1; i <= Y; i++) {
		for (int j = 1; j <= X; j++) {
			if (a[i][j] != 0 || check[i][j]) continue;

			check[i][j] = true;
			ans.push_back(make_pair(i,j));

			go(i, j);

			ans.pop_back();
			check[i][j] = false;

		}
	}

}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	input();

	go(0,0);

	printf("%d",maxcnt);
}

느낀점

• 체크할 것이 많아 시간이 좀 오래걸렸지만 전형적인 BFS 문제였다.