[#14502] 연구소

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;
vector<vector<int>> board;
vector<pair<int, int>> virus;  //바이러스 좌표
int ans = -1;

//동서남북
int dRow[4] = { 0, 0, 1, -1 };
int dCol[4] = { 1, -1, 0, 0 };

//cnt번째 벽을 row, col에 세울거야
void recursive(int cnt, int row, int col) {
	if (cnt == 4) {
		//기저
		
		//바이러스 위치를 시작으로 bfs 돌리기
		vector <vector<bool>> discover(n, vector<bool>(m, false));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 1)
					discover[i][j] = true;  //벽이면 bfs 돌릴 때 가면 안되니까 discover true로 해주고 안가게
			}
		}

		//바이러스 위치를 시작으로 bfs 돌리기
		for (int v = 0; v < virus.size(); v++) {
			//bfs 시작 위치 (바이러스 위치)
			int startRow = virus[v].first;
			int startCol = virus[v].second;

			queue<pair<int, int>> q;
			q.push({ startRow, startCol });
			discover[startRow][startCol] = true;

			while (!q.empty()) {
				int hereRow = q.front().first;
				int hereCol = q.front().second;
				q.pop();

				//동서남북
				for (int i = 0; i < 4; i++) {
					int thereRow = hereRow + dRow[i];
					int thereCol = hereCol + dCol[i];

					//범위내이고 
					if (0 <= thereRow && thereRow < n &&
						0 <= thereCol && thereCol < m && 
						!discover[thereRow][thereCol]) {
						//범위안에 있고 큐에 들어간적없으면
						q.push({ thereRow, thereCol });
						discover[thereRow][thereCol] = true;
					}
				}
			}
		}

		//바이러스가 퍼지지 않은 곳 세기
		int tempAns = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!discover[i][j])
					tempAns++;
			}
		}

		ans = max(ans, tempAns);

		return;
	}

	vector<vector<int>> tempBoard = board;  //원상태로 돌리기 위해

	bool isFirst = true;
	for (int i = row; i < n;  i++) {
		for (int j = 0; j < m; j++) {
			//전 재귀에서 본 좌표 다음부터 보기 위해서
			if (i == row && isFirst) {
				isFirst = false;
				j = col;
				if (j >= m)
					continue;
			}

			if (board[i][j] == 0) {
				//빈칸이면 벽 세우기
				board[i][j] = 1;
				recursive(cnt + 1, i, j + 1);
				board = tempBoard;  //원 상태로 돌리기 (벽 없애기)
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	board = vector<vector<int>>(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &board[i][j]);

			if (board[i][j] == 2) {
				//바이러스라면
				virus.push_back({ i,j });
			}
		}
	}

	//////////////////////////

	recursive(1, 0, 0);
	cout << ans;

	return 0;
}

 

완전탐색 + BFS (또는 DFS)

Visual studio에서 테스트케이스 돌렸을 때 너무 오래걸리길래 시간 줄여볼 방법 생각해보다가 그냥 제출했는데 제출됨.... 컴퓨터 과부하 걸렸나 좀 쉬어줘야지

둘 다 풀 수 있으니까 BFS 할까 DFS 할까 고민했는데 DFS 쓰면 재귀함수가 두개가 되는게 꼴보기 싫어서 그냥 BFS....

 

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

14502번: 연구소