[백준][bfs] 14502 연구소 c++ 구현

목차

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

문제

 

 

문제 구현 방향

범위가 적으므로 모든 벽에 대한 경우를 다 해보는 방향으로 풀었다. 그 후 바이러스에 대한 BFS로 배열을 채우고 0에 대한 BFS로 탐색을 진행해 모든 면적을 구한 뒤 가장 큰 값을 출력 해 주었다.

 

 

문제 풀이 시 필요한 아이디어

• 모든 경우의 수를 하기위해 순열을 만드는 방법
• 매번 탐색을 위한 배열의 초기화

 

 

문제 풀이 시 참고하면 좋습니다..

https://be-senior-developer.tistory.com/49

[알고리즘] 순열과 조합 c++ 구현

 

간략하게 순열 코드는 다음과 같다.

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

using namespace std;
vector<int>v;

int n = 5, k = 3, a[5] = { 1, 2, 3, 4, 5 };
void print(vector<int>& v) {
	for (int i : v)cout << i << " ";
	cout << "\n";
}

void combi(int start, vector<int> b) {
	if (b.size() == k) {
		print(b);
		return;
	}
	for (int i = start; i < n; i++) {
		b.push_back(i);
		combi(i+1, b);
		b.pop_back();
	}
}

 

코드 구현

#include <iostream>
#include<map>
#include<math.h>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;

int original[100][100];  //원본 배열
int board[100][100];  //복사본 배열
int visit[100][100] = { 0 };

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int N, M;

vector<int>v;
vector<int>cntv;

void bfs_virus(int start_x, int start_y) {  //바이러스 퍼짐 bfs
	queue<pair<int, int>> q;
	q.push(make_pair(start_x, start_y));
	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 > M - 1 || ny > N - 1)
				continue;
			if (board[ny][nx] == 1 || board[ny][nx] == 2)
				continue;
			q.push(make_pair(nx, ny));
			board[ny][nx] = 2;
		}
	}

}

void reset() {  //초기화 해주는 함수
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			board[i][j] = original[i][j];
			visit[i][j] = 0;
		}
	}
}

int blocks(vector<int>& v) {
	for (int i : v) {
		if (board[i / M][i % M] == 2 || board[i / M][i % M] == 1) {
			return 1;
		}
		if (board[i / M][i % M] == 0)
			board[i / M][i % M] = 1;
	}
	return 0;
}

void combi(int start, vector<int>& b) {
	if (b.size() == 3) {
		int cnt = 0;
		reset();
		if (blocks(b))
			return;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 2)
					bfs_virus(j, i);
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 0) {  //0의 개수만 세어주면 됨
					cnt++;
				}
			}
		}
		cntv.push_back(cnt);
		return;
	}
	for (int i = start; i < M * N; i++) {
		b.push_back(i);
		combi(i + 1, b);
		b.pop_back();
	}
}

int main() {
	cin >> N >> M;
	int mcnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> original[i][j];
		}
	}
	combi(0, v);

	mcnt = *max_element(cntv.begin(), cntv.end()); //가장 큰 값 출력
	cout << mcnt;

}