백준 14502 - 연구소(C++)

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

14502번: 연구소

DFS를 통해서 벽을 선택한후, BFS를 통해서 탐색하는 문제였습니다.

 

(문제는 너무 길어서 생략하겠습니다)

 

문제 접근 방법

1. 입력을 받음과 동시에 빈칸을 저장한다.

2. 빈칸 중에서 3개를 순차적으로 고른다.

3. 고른 빈칸에 벽을 세운뒤 BFS 탐색을 통해서 바이러스를 퍼트린다.

4. 안전 영역을 구한다.

5. 벽이 전부 선택될 때까지 반복한다.

 

문제 접근 방법 - 1번

for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			map_new[i][j] = map[i][j];
			if (map[i][j] == 0) Select.push_back(make_pair(i, j));
		}
	}

map_new[][] 배열에는 "기존의 바이러스와 벽의 위치 + 새로 세운 벽"의 정보를 담을 배열입니다.

BFS 탐색에 map_new 배열을 사용할 것입니다.

빈 벽의 위치는 Select 백터에 저장했습니다.

 

문제 접근 방법 - 2번 + 4번 + 5번

int select_wall(int start, int cnt) {
	if (cnt == 3) {
		for (int i = 0; i < 3; i++) {
			map_new[wall[i].first][wall[i].second] = 1;
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (map_new[i][j] == 2 && check[i][j] == 0) {
					check[i][j] = 1;
					bfs(i, j);
				}
			}
		}
		int size_safe = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (map_new[i][j] == 0) {
					size_safe++;
				}
			}
		}
		answer = max(answer, size_safe);
		memset(check, 0, sizeof(check));
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				map_new[i][j] = map[i][j];
			}
		}
	}
	else{
		for (int i = start; i < Select.size(); i++) {
			if (check_wall[Select[i].first][Select[i].second] == 1) continue;
			check_wall[Select[i].first][Select[i].second] = 1;
			wall.push_back(Select[i]);
			select_wall(i, cnt + 1);
			wall.pop_back();
			check_wall[Select[i].first][Select[i].second] = 0;
		}
    }
	return answer;
}

Select 백터에는 빈 벽의 위치가 저장되어 있습니다. 

 

여기서 생각해봐야 하는게 (1번 + 2번 + 3번) 과 (3번 + 2번 + 1번) 벽들이 선택된거는 같은 경우입니다. 따라서 DFS를 통해서 (1번 + 2번 + 3번) ~ (N-2번, N-1번, N번) 벽까지 순차적으로 선택해야합니다. 

위와 같은 방식으로 벽을 3개 선택을 했다면  map_new 배열에 새로 벽을 세워줍니다. 그 뒤에 BFS 탐색을 실행한 뒤, 안전한 영역의 갯수를 구합니다. 

 -> 위의 방식을 벽을 전부 선택할 때까지 반복합니다.(한번 실행이 끝날때마다 map_new, check배열은 reset합니다.)

 

문제 접근 방법 - 3번

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		int x1 = q.front().first;
		int y1 = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + dx[i];
			int yy = y1 + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (check[xx][yy] == 0 && map_new[xx][yy] == 0) {
					check[xx][yy] = 1;
					map_new[xx][yy] = 2;
					q.push(make_pair(xx, yy));
				}
			}
		}
	}
}

BFS 탐색 코드입니다.

바이러스가 있는 곳의 위치부터 시작해 상하좌우 탐색을 합니다. 

이전에 방문하지 않았으며 빈공간일 경우 -> 해당 좌표를 기준으로 탐색을 다시 시작합니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M;
int map[9][9];
int check[9][9];
int check_wall[9][9];
int map_new[9][9];
int answer = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int>> Select;
vector<pair<int, int>> wall;

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		int x1 = q.front().first;
		int y1 = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + dx[i];
			int yy = y1 + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (check[xx][yy] == 0 && map_new[xx][yy] == 0) {
					check[xx][yy] = 1;
					map_new[xx][yy] = 2;
					q.push(make_pair(xx, yy));
				}
			}
		}
	}
}

int select_wall(int start, int cnt) {
	if (cnt == 3) {
		for (int i = 0; i < 3; i++) {
			map_new[wall[i].first][wall[i].second] = 1;
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (map_new[i][j] == 2 && check[i][j] == 0) {
					check[i][j] = 1;
					bfs(i, j);
				}
			}
		}
		int size_safe = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (map_new[i][j] == 0) {
					size_safe++;
				}
			}
		}
		answer = max(answer, size_safe);
		memset(check, 0, sizeof(check));
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				map_new[i][j] = map[i][j];
			}
		}
	}
	else{
		for (int i = start; i < Select.size(); i++) {
			if (check_wall[Select[i].first][Select[i].second] == 1) continue;
			check_wall[Select[i].first][Select[i].second] = 1;
			wall.push_back(Select[i]);
			select_wall(i, cnt + 1);
			wall.pop_back();
			check_wall[Select[i].first][Select[i].second] = 0;
		}
    }
	return answer;
}

void solve() {
	int ans = select_wall(0, 0);
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			map_new[i][j] = map[i][j];
			if (map[i][j] == 0) Select.push_back(make_pair(i, j));
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!