백준 14502 연구소

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

※선행해야 할 알고리즘 : BFS/DFS

Algorithm 요약 : 벽을 3개를 임의의 위치에 놓고 상하좌우로 퍼지는 바이러스가 비어있는 곳에 퍼졌을 때 안전한 구간의 개수의 최대값를 출력하시오.

1. 2는 바이러스, 1은 벽, 0은 비어있는 곳 이라고 할 때, 비어있는 0에 벽을 임의로 3개를 세운다.

이 작업은 재귀함수로 진행하며 벽을 3개 세움과 동시에 BFS를 진행하여 반환해주고 다시 0으로 바꿔야한다.(그래야 recorvery 이후에 다음 벽을 세우기 때문에)

입력 예제 2를 예로 들면 다음과 같다

첫 번째 세워진 벽3개는

1 1 1 0 0 0

1 0 0 0 0 2

1 1 1 0 0 2

0 0 0 0 0 2

두 번째 세워진 벽 3개는

1 1 0 1 0 0

1 0 0 0 0 2

1 1 1 0 0 2

0 0 0 0 0 2

.

.

.

이때, 반드시 원본이 복사되어 있는 temp배열을 활용해야 한다. 원본이 날아가면 다음에 1을 세울 구간을 모르기 때문이다.

2. 이런식으로 벽을 세운 후 2를 기준으로 BFS를 진행한 후 count 된 값을 vector에 삽입해 최대값을 출력해 내는 것이다.

3. 1~2를 queue를 활용하여 BFS를 진행하면 다음과 같다.

//kuklife.tistory.com #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef vector<vector<int>> two_vector; vector<int> result; queue<pair<int, int>> q; int N, M; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; void search(two_vector temp) { for (int i = 0; i < temp.size(); i++) for (int j = 0; j < temp[i].size(); j++) if (temp[i][j] == 2) q.push({ i,j }); } void bfs(two_vector temp) { search(temp); while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny >= 0 && ny < N && nx >= 0 && nx < M && !temp[ny][nx]) { q.push({ ny,nx }); temp[ny][nx] = 2; } } } int count = 0; for (int i = 0; i < temp.size(); i++) for (int j = 0; j < temp[i].size(); j++) if (temp[i][j] == 0) count++; result.push_back(count); } void sol(two_vector temp, int n) { if (n == 1) { bfs(temp); return; } for (int i = 0; i < temp.size(); i++) { for (int j = 0; j < temp[i].size(); j++) { if (!temp[i][j]) { temp[i][j] = 1; sol(temp, n - 1); temp[i][j] = 0; } } } } int main() { two_vector G; cin >> N >> M; G.resize(N); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int x; cin >> x; G[i].push_back(x); } } auto temp = G; for (int i = 0; i < G.size(); i++) { for (int j = 0; j < G[i].size(); j++) { if (!G[i][j]) { temp = G; temp[i][j] = 1; sol(temp, 3); temp[i][j] = 0; } } } cout << *max_element(result.begin(), result.end()) << endl; return 0; }