[Baekjoon/C++] 14502번 연구소

14502번 백준 - 연구소

 

문제 링크: https://www.acmicpc.net/problem/14502

 

 

문제 접근 방법:

1. 벽 세울 수 있는 모든 경우의 수 찾기

2. 벽 3개 세운 뒤 bfs 돌리기

 

 

코드:

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

int N, M;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int arr[10][10];
int copyArr[10][10];
int visited[10][10] = { 0, };
queue < pair<int, int>>q;
int cnt = 0; 
int maxNum = -1;


vector<pair<int, int>> virus;


void printMap(void) {
	cout << "\n\n";
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << copyArr[i][j] << " ";
		}
		cout << "\n";
	}
}

void init() {
	cnt = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			copyArr[i][j] = arr[i][j];
	//memcpy(arr, copyArr, sizeof(arr));

	//printMap();
	while (!q.empty()) {
		q.pop();
	}
}

int bfs() {
	for (int i = 0; i < virus.size(); i++)
		q.push({ virus[i].first, virus[i].second });
	
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx >= 0 && ny >= 0 && nx < N && ny < M && copyArr[nx][ny] == 0) {
				q.push({ nx,ny });
				copyArr[nx][ny] = 2;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (copyArr[i][j] == 0) {
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <M; j++) {
			cin >> arr[i][j];

			if (arr[i][j] == 2)
				virus.push_back({ i,j });
		}
	}

	//init();

	int ir, ic, jr, jc, kr, kc;

	for (int i = 0; i < N * M; i++) {
		for (int j = i + 1; j < N * M; j++) {
			for (int k = j + 1; k < N * M; k++) {
				ir = i / M;
				ic = i % M;
				jr = j / M;
				jc = j % M;
				kr = k / M;
				kc = k % M;

				if (arr[ir][ic] != 0 || arr[jr][jc] != 0 || arr[kr][kc] != 0) {
					continue;
				}

				init();

				copyArr[ir][ic] = 1;
				copyArr[jr][jc] = 1;
				copyArr[kr][kc] = 1;


				maxNum = max(bfs(), maxNum);

				//printMap();
			}
		}
	}
	cout << maxNum;
}