백준 14502번 연구소 C++

리뷰

재귀와 BFS가 결합된 형태로 문제를 풀었다.

 

문제 풀이

1. n, m을 입력받고 n * m 크기의 2차 배열에 값을 받아준다. 이때 값이 2일경우 해당 좌표를 큐에 미리 추가해 둔다.
2. 2차 배열을 순회하며 만약 값이 0인 좌표를 만난다면 해당 값을 1로 변경하고 현재 좌표 및 설치한 벽의 개수 1개를 wall함수의 인자로 전달해 실행해 준다. 이후 1로 변경한 값을 다시 0으로 변경한다.
3. wall 함수는 위에서 0으로 바꿨던 좌표 위치부터 2차 배열을 순회하고 0을 만났다면 1로 변경, 벽의 개수 증가.
4. 만약 벽의 개수가 3개라면 dfs실행, 아니라면 wall을 재귀 호출한다. 이후 다시 0으로 변경, 벽의 개수 감소.
5. bfs 함수에서는 현재 2차 배열과 큐를 깊은 복사를 해주고 넓이 우선 탐색을 진행해 준다.
6. while루프가 종료된 후 2차 배열을 순회하여 0의 개수를 세어주고 최대값을 계속 갱신해 준다.
7. 모든 벽설치와 bfs 탐색이 끝난 후 0의 최대 개수를 출력해 주면 된다.

 

참고 사항

2의 위치는 고정이므로 2차 배열을 입력 받을때 큐를 전역변수로 만들어 놓으면 좋다.

 

 

정답 코드

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

using namespace std;

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

int n, m, min_wall = 0;
vector<vector<int>> lst;

struct pos {
	int x, y;
};

queue<pos> dq;

void bfs() {
	vector<vector<int>> v = lst;
	queue<pos> q = dq;

	while (!q.empty()) {
		pos now = q.front();
		q.pop();
		int cx = now.x, cy = now.y;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
				v[nx][ny] = 2;
				q.push({ nx, ny});
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (v[i][j] == 0) sum++;
		}
	}
	min_wall = max(min_wall, sum);
}

void wall(int x, int y, int done) {
	for (int i = x; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i == x && j < y) continue;
			if (lst[i][j] == 0) {
				lst[i][j] = 1;
				done++;
				if (done == 3) bfs();
				else wall(i, j, done);
				lst[i][j] = 0;
				done--;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	lst.resize(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int num;
			cin >> num;
			lst[i][j] = num;
			if (num == 2) dq.push({ i, j });
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 0) {
				lst[i][j] = 1;
				wall(i, j, 1);
				lst[i][j] = 0;
			}
		}
	}
	cout << min_wall;
}