이번에는 백준 14502번 연구소 문제를 풀어보았습니다.
이 문제는 연구소의 빈칸 중 정확히 3곳에 벽을 세운 뒤, 바이러스가 퍼지고 남는 안전 영역의 최대 크기를 구하는 문제입니다.
핵심은 크게 두 가지였습니다.
- 빈칸 중 3개를 선택하는 조합
- 그 상태에서 바이러스가 퍼지는 범위를 구하는 DFS
즉, 벽을 세울 위치를 모두 시도해보고, 각 경우마다 바이러스 확산 결과를 계산하는 방식으로 해결할 수 있었습니다.
문제 설명
연구소는 N x M 크기의 격자로 주어지고, 각 칸은 다음 중 하나입니다.
0: 빈 칸1: 벽2: 바이러스
새로 세울 수 있는 벽은 정확히 3개이고,
바이러스는 상하좌우 인접한 빈 칸으로 퍼질 수 있습니다.
벽을 3개 세운 뒤 바이러스가 모두 퍼지고 나서,
퍼지지 않고 남아 있는 빈 칸의 개수 중 최댓값을 구하면 됩니다.
풀이 아이디어
이 문제는 모든 빈칸 중에서 3개를 고르는 경우를 전부 시도해보면 됩니다.
그래서 먼저 빈칸 위치들을 전부 empty_cells에 저장해두고,
이 중 3개를 고르는 조합을 3중 반복문으로 만들었습니다.
그리고 각 조합마다
- 선택한 3칸을 벽으로 바꾸고
- 바이러스 위치에서 DFS를 돌려 퍼질 수 있는 칸을 방문 처리하고
- 마지막에 안전 영역 개수를 세고
- 다시 visited를 초기화하고, 벽도 원래대로 되돌리는
방식으로 구현했습니다.
즉, 전체 구조는
벽 3개 선택 → 바이러스 확산 → 안전 영역 계산 → 원상복구
로 볼 수 있습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int N,M;
int max_cnt;
int dy[4] = {0,1,0,-1};
int dx[4] = {1,0,-1,0};
vector<vector<int>> inp_map;
vector<vector<int>> visited;
vector<pair<int, int>> empty_cells;
void dfs(int y, int x) {
visited[y][x] = 1;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx]) continue;
if (inp_map[ny][nx] == 1)
continue;
dfs(ny, nx);
}
}
void solve(pair<int, int> first, pair<int, int> second, pair<int, int> third) {
inp_map[first.first][first.second] = 1;
inp_map[second.first][second.second] = 1;
inp_map[third.first][third.second] = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (inp_map[i][j] == 2 && visited[i][j] == 0) {
dfs(i, j);
}
}
}
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (inp_map[i][j] == 2 || visited[i][j] == 1 || inp_map[i][j] == 1) continue;
cnt++;
}
}
if (cnt > max_cnt) max_cnt = cnt;
for (int i = 0; i < visited.size(); i++) {
fill(visited[i].begin(), visited[i].end(), 0);
}
inp_map[first.first][first.second] = 0;
inp_map[second.first][second.second] = 0;
inp_map[third.first][third.second] = 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
inp_map.push_back(vector<int>());
visited.push_back(vector<int>());
for (int j = 0; j < M; j++) {
int temp;
cin >> temp;
inp_map[i].push_back(temp);
visited[i].push_back(0);
if (temp == 0)
empty_cells.push_back(make_pair(i, j));
}
}
for (int i=0; i<empty_cells.size(); i++) {
for (int j=i+1; j<empty_cells.size(); j++) {
for (int k=j+1; k<empty_cells.size(); k++) {
solve(empty_cells[i], empty_cells[j], empty_cells[k]);
}
}
}
cout << max_cnt << endl;
return 0;
}풀이 흐름
- 연구소 지도를 입력받는다.
- 빈칸인 위치들을
empty_cells에 저장한다. - 빈칸들 중 3개를 고르는 모든 조합을 만든다.
- 각 조합마다
solve()를 호출한다. solve()에서는 선택한 세 칸을 벽으로 만든다.- 모든 바이러스 위치에서 DFS를 돌려 감염되는 칸을
visited로 표시한다. - 감염되지 않은 빈칸 수를 세어 안전 영역 크기를 구한다.
- 최댓값을 갱신한다.
visited를 초기화하고, 세웠던 벽도 다시 빈칸으로 되돌린다.- 모든 조합을 확인한 뒤 최댓값을 출력한다.
구현 포인트
1. 빈칸 위치를 먼저 저장
이 문제는 벽을 세울 수 있는 위치가 빈칸뿐이기 때문에,
처음 입력을 받을 때 빈칸 좌표를 따로 모아두었습니다.
if (temp == 0)
empty_cells.push_back(make_pair(i, j));이렇게 해두면 이후에는 전체 맵을 다시 보지 않고,
빈칸 목록만 가지고 벽을 세울 후보를 선택할 수 있습니다.
2. 빈칸 3개를 고르는 조합
벽은 정확히 3개를 세워야 하므로,
empty_cells 중에서 3개를 고르는 조합을 만들었습니다.
for (int i=0; i<empty_cells.size(); i++) {
for (int j=i+1; j<empty_cells.size(); j++) {
for (int k=j+1; k<empty_cells.size(); k++) {
solve(empty_cells[i], empty_cells[j], empty_cells[k]);
}
}
}이 구조를 통해 같은 위치를 중복해서 고르지 않으면서,
가능한 모든 3개 조합을 확인할 수 있습니다.
즉, 이 문제에서 벽 배치는 조합 문제로 볼 수 있습니다.
3. 선택한 세 칸을 벽으로 바꾸기
solve()에 들어오면 먼저 선택한 세 위치를 벽으로 바꿉니다.
inp_map[first.first][first.second] = 1;
inp_map[second.first][second.second] = 1;
inp_map[third.first][third.second] = 1;이렇게 해서 현재 조합에 대해 실제로 벽을 세운 상태를 만든 뒤,
그 상태에서 바이러스 확산을 계산합니다.
4. 바이러스 퍼뜨리기 DFS
이후 맵 전체를 돌면서 바이러스인 칸(2)에서 DFS를 시작합니다.
if (inp_map[i][j] == 2 && visited[i][j] == 0) {
dfs(i, j);
}DFS에서는 벽만 막고, 나머지 칸으로 계속 퍼질 수 있도록 했습니다.
if (inp_map[ny][nx] == 1)
continue;
dfs(ny, nx);즉, visited는 현재 벽 배치에서 바이러스가 도달 가능한 칸들을 표시하는 역할을 합니다.
5. 안전 영역 개수 세기
DFS가 끝난 뒤에는 안전 영역 개수를 셉니다.
if (inp_map[i][j] == 2 || visited[i][j] == 1 || inp_map[i][j] == 1) continue;
cnt++;여기서 세지 않는 칸은
- 원래 바이러스가 있는 칸
- DFS로 감염된 칸
- 벽인 칸
입니다.
즉, 벽도 아니고, 바이러스도 아니고, 감염도 안 된 칸만 세어서 안전 영역 크기를 구합니다.
6. 원상복구
한 조합 계산이 끝나면 다음 조합을 위해 상태를 다시 되돌려야 합니다.
먼저 visited를 전부 0으로 초기화합니다.
for (int i = 0; i < visited.size(); i++) {
fill(visited[i].begin(), visited[i].end(), 0);
}그리고 방금 세웠던 세 개의 벽도 다시 빈칸으로 바꿉니다.
inp_map[first.first][first.second] = 0;
inp_map[second.first][second.second] = 0;
inp_map[third.first][third.second] = 0;이 과정이 있어야 다음 조합을 독립적으로 다시 시도할 수 있습니다.
