<Baekjoon> #14502 BFS_Laboratory c++

#14502 연구실
처음에 문제를 잘못 읽어서 바이러스가 바이러스 점을 기준으로 8방향으로 모두 퍼질 수 있다고 생각했고 이차원 배열을 call by value로 넘기려고 해서 큰 문제가 발생했었다..!

먼저 한 빈 공간을 기준으로 인접한 빈 공간부터 차례대로 3개씩 벽을 쌓아나가서 바이러스가 최소로 퍼질 수 있는 것을 구해야 한다.

1. map생성 및 초기화

	vector<vector<int>> map(n, vector<int>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

(위에서 말한대로 처음에는 int map[MAX][MAX]로 생성 했다가 파라미터로 넘길 때 문제가 발생해서 다시 바꿨다.)

const int EMPTY = 0;
const int WALL = 1;
const int VIRUS = 2;

그리고 직관적으로 보이기 위해 각각의 이름을 지정해주었다.

2. make wall

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == EMPTY)
				makeWall(map, i, j,1);
		}
	}

map위의 모든 Empty공간에 대해서 조사를 해야하므로 이중 for문을 이용해 찾았고 makeWall 함수에서 벽을 3개 만들 것이다.

(여기서 원래 내가 입력받은 map은 영구적으로 변경되면 안 되므로 call by value값으로 넘겨주어야 하는데, 이차원 벡터는 인자로 넘길 때 call by reference밖에 안 된다. 그래서 vector로 선언해야 한다. 그렇게 하기 싫으면 map을 복사해도 된다.)

makeWall함수는 4개를 인자로 가지고 있다.
makeWall(vector<vector<int>> map, int y, int x, int cnt)
y,x는 현재 map위에서의 위치고, cnt는 현재까지 만든 벽의 개수다. 만약 벽이 3개가 되면 bfs함수로 가서 바이러스가 퍼진 뒤 Empty공간의 개수를 구해서 최대값을 갱신한다.

3. bfs
   bfs(vector<vector<int>> &map)
   bfs 함수 내 구현은 일반 bfs 함수의 구현과 크게 다른 점이 없다.
   queue<pair <int, int>>q를 만들고 q에는 Virus 좌표를 넣어주고 인접한 Empty좌표에 대해 pop, push 를 반복하며 Virus를 전파해준다.

여기서 makeWall 함수에서 벽을 만들었던 map을 그대로 가져와야 하기 때문에 call by reference로 가져왔다. 이 부분이 제일 헷갈렸던 부분이다.

전체코드

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

using namespace std;

int n, m;
const int EMPTY = 0;
const int WALL = 1;
const int VIRUS = 2;
int result = 0;

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

void bfs(vector<vector<int>> &map) {
	queue <pair<int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == VIRUS)
				q.push(make_pair(i, j));
		}
	}
	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx_y = cur_y + dy[i];
			int nx_x = cur_x + dx[i];
			if (nx_y<0 || nx_x<0 || nx_y>=n || nx_x>=m) continue;
			if (map[nx_y][nx_x] == EMPTY) {
				q.push(make_pair(nx_y, nx_x));
				map[nx_y][nx_x] = VIRUS;
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (map[i][j] == EMPTY) cnt++;
	result = max(result, cnt);
}
void makeWall(vector<vector<int>> map, int y, int x, int cnt) {
	map[y][x] = WALL;
	if (cnt == 3) {
		bfs(map);
		return;
	}
	for (int i = y; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == EMPTY)
				makeWall(map, i, j, cnt + 1);
		}
	}
}
int main() {
	cin >> n >> m;
	vector<vector<int>> map(n, vector<int>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == EMPTY)
				makeWall(map, i, j,1);
		}
	}
	cout << result << endl;
	return 0;
}