BOJ 14502. 연구소
문제 설명
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
[입력]
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0[출력]
27[입력]
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2[출력]
9[입력]
8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0[출력]
31. 문제 해석
• N×M 크기의 직사각형 지도가 있고, 1×1 크기의 칸으로 나누어져 있다. (3≤N, M≤8)
• 칸: 빈칸,벽
• 일부 빈 칸에는 바이러스가 있고, 인접한 빈 칸으로 계속해서 퍼져 나간다.
•벽을 3개 세워서 → 바이러스가 퍼질 수 없는 곳의 크기를 구하는 문제
삼성 SW 역량테스트 기출문제의 최근 출제 경향을 보면, 완전탐색 + BFS/DFS와 같은 형태로 출제되는 경향이 있다. 게리맨더링 문제도 완전탐색 + BFS/DFS의 형태로 풀이할 수 있었다. 이때 항상 주의할 점은 완전탐색에서 누락된 부분이 있는가? 그리고 주어진 조건을 빠짐없이 충족하는가? 이다.
이렇게 큰 문제는 작은 문제들로 쪼개어서 생각해보면 조금 더 생각하기가 쉽다. 1) 벽을 3개 세운다. 2) 바이러스가 퍼지는 영역을 구한다.(최종적으로는 퍼질 수 없는 영역을 구한다.) 이 두가지를 따로 따로 생각하고 각각의 함수로 구현한 후, 마지막에 합치면 된다.
✓ 바이러스가 퍼지는 영역 구하기(→ 바이러스가 퍼지지 않은 영역 구하기)
여기서 벽을 세운다는 내용을 제외한다면, 입력으로 주어진 상태에서 바이러스가 있는 지점에서 부터 DFS or BFS로 완전탐색을 하면 확산된 영역이 처리된다. 그러면 바이러스가 퍼질 수 없는 영역의 크기도 구할 수 있다.
칸은 정점, 인접한 칸의 관계는 간선으로 나타내면, 바이러스에서 시작해서 연결된 모든 정점을 방문하는 문제가 되어버리기 때문이다. 이때 시간복잡도는 맵을 모두 탐색하므로 O(NxM)가 된다.
이때는 '한 정점에서 모든 정점을 방문한다'는 DFS와 BFS의 기본 성질을 이용하는 문제가 되므로 BFS와 DFS중 어느것을 사용해도 풀이가 가능하다. ( cf. 바이러스의 최소 확산횟수를 구하는 문제였다면 BFS만 사용해야 했을 것이다. )
마지막으로, 바이러스가 퍼지지 않은 영역을 구하기 위해서는 NxM만큼 탐색하면서 0인 칸을 모두 구하면 된다. 이 부분도 마찬가지로 시간복잡도는 O(NxM)이다.
✓ 벽 3개 세우기
지도의 모든 칸에 벽을 3개 세워보는 방법으로 구현한다면, 벽을 3개 세우는 경우의 수는 (NxM)^3 가지가 된다.
(NxM 중에 첫 번째 벽 세우기) x (NxM 중에 두 번째 벽 세우기) x (NxM 중에 세 번째 벽 세우기)
벽을 세운 다음 안전 영역의 크기를 구하는 방법은 벽이 없을때와 마찬가지로 BFS 또는 DFS로 탐색하여 O(NxM)가 된다. 그러면 총 시간복잡도는 O((NxM)^4)가 나오는데, N, M ≤ 8 이기 때문에, 충분히 시간 안에 해결할 수 있다.
(8x8)^4 = 64^4 = (2^6)^4 = 2^24 = 16,777,216
2. 문제 풀이
먼저, 벽 3개가 이미 다 세워졌다고 가정하고 DFS나 BFS를 이용해서 바이러스가 퍼지도록 동작하는 함수를 구현해본다.
BFS로 바이러스 퍼뜨리기 구현
int bfs() {
queue<pair<int,int>> q;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
b[i][j] = a[i][j];
if (b[i][j] == 2) // 바이러스의 위치를 전부 큐의 시작점으로 넣어둠
q.push(make_pair(i,j));
}
}
while (!q.empty()) {
int x = q.front().first; int y = q.front().second; q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k]; int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (b[nx][ny] == 0) { // 바이러스가 퍼질 수 있는 칸에 퍼뜨림
b[nx][ny] = 2;
q.push(make_pair(nx,ny));
}
}
}
}
int cnt = 0; // 바이러스가 퍼지지 않은 영역을 구한다.
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++)
if (b[i][j] == 0) cnt += 1;
}
return cnt;
}DFS로 바이러스 퍼뜨리기 구현
void dfs(int x, int y) {
for (int k=0; k<4; k++) {
int nx = x+dx[k], ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (b[nx][ny] == 0) { // 빈 칸이면 바이러스 퍼뜨림
b[nx][ny] = 2;
dfs(nx,ny);
}
}
}
}
int spread() { // 바이러스를 퍼뜨려보고 퍼지지 않은 영역의 개수를 리턴
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++)
b[i][j] = a[i][j]; // 지도를 복사
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++)
if (b[i][j] == 2) dfs(i, j); // 바이러스가 있는 각 지점에서 DFS
}
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++)
if (b[i][j] == 0) cnt += 1; // 안전영역의 개수를 누적
}
return cnt;
}DFS/BFS로 바이러스를 퍼뜨리고, 퍼질수 없는 영역을 구하는 함수를 만들었으니, 이제 벽 3개를 지도상의 모든 칸에 놓는 경우를 만들고, 그때마다 DFS/BFS함수를 호출하는 방식으로 동작하면 될 것이다.
벽 3개를 놓는 모든 경우를 완전탐색
int main() {
...
int ans = 0;
for (int x1=0; x1<n; x1++) { // 첫 번째 벽의 위치 지정
for (int y1=0; y1<m; y1++) {
if (a[x1][y1] != 0) continue; // 벽을 놓을 위치가 빈 칸이 아니면 다시 시작
for (int x2=0; x2<n; x2++) { // 두 번째 벽의 위치 지정
for (int y2=0; y2<m; y2++) {
if (a[x2][y2] != 0) continue; // 벽을 놓을 위치가 빈 칸이 아니면 다시 시작
for (int x3=0; x3<n; x3++) { // 세 번째 벽의 위치 지정
for (int y3=0; y3<m; y3++) {
if (a[x3][y3] != 0) continue; // 벽을 놓을 위치가 빈 칸이 아니면 다시 시작
if (x1 == x2 && y1 == y2) continue;
if (x1 == x3 && y1 == y3) continue;
if (x2 == x3 && y2 == y3) continue;
a[x1][y1] = 1; a[x2][y2] = 1; a[x3][y3] = 1; // 세 개의 벽을 놓고
int cur = bfs(); // BFS 탐색을 돌고
if (ans < cur) ans = cur; // 안전영역을 최댓값으로 갱신
a[x1][y1] = 0; a[x2][y2] = 0; a[x3][y3] = 0; // 다시 원래대로 바꾼다.
}
}
}
}
}
}
cout << ans << '\n';
return 0;
}이렇게 x, y 좌표를 모두 바꾸어가면서 벽 3개를 모두 놓아보아야 하므로, 최종적으로 6중 for문이 만들어진다. 보통은 4중 for문 이상으로 올라가면 '내가 잘못 구현하고 있나?'라는 생각이 들기 마련이다. 하지만 삼성 SW 역량테스트의 출제경향을 보면 기본적으로 4중 for문 이상으로 많이 올라간다. 이는 이차원 배열 상에서 완전탐색을 구현해야 하므로 어쩔 수 없다. 하지만 단순히 모든 x, y 좌표를 이동한다는 점에서 그 틀은 거의 유사한 형태이므로 당황하지 않고 크게 생각하면 된다.
BFS를 활용한 구현
#include <iostream>
#include <queue>
using namespace std;
int n, m;
int a[10][10];
int b[10][10];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int bfs() {
queue<pair<int,int>> q;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
b[i][j] = a[i][j];
if (b[i][j] == 2) { // 바이러스의 위치를 전부 큐의 시작점으로 넣어둠
q.push(make_pair(i,j));
}
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (b[nx][ny] == 0) { // 바이러스가 퍼질 수 있는 칸에
b[nx][ny] = 2; // 바이러스 퍼뜨림
q.push(make_pair(nx,ny));
}
}
}
}
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (b[i][j] == 0) { // 빈칸의개수를 센다
cnt += 1;
}
}
}
return cnt;
}
int main() {
cin >> n >> m;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> a[i][j];
}
}
int ans = 0;
for (int x1=0; x1<n; x1++) { // 벽1
for (int y1=0; y1<m; y1++) {
if (a[x1][y1] != 0) continue;
for (int x2=0; x2<n; x2++) { // 벽2
for (int y2=0; y2<m; y2++) {
if (a[x2][y2] != 0) continue;
for (int x3=0; x3<n; x3++) { // 벽3
for (int y3=0; y3<m; y3++) {
if (a[x3][y3] != 0) continue;
if (x1 == x2 && y1 == y2) continue;
if (x1 == x3 && y1 == y3) continue;
if (x2 == x3 && y2 == y3) continue;
a[x1][y1] = 1; // 세 개의 벽을 놓고
a[x2][y2] = 1;
a[x3][y3] = 1;
int cur = bfs(); // BFS 탐색을 돌고
if (ans < cur) ans = cur;
a[x1][y1] = 0; // 다시 원래대로 바꾸어준다.
a[x2][y2] = 0;
a[x3][y3] = 0;
}
}
}
}
}
}
cout << ans << '\n';
return 0;
}DFS를 활용한 구현
#include <iostream>
#include <queue>
using namespace std;
int n, m;
int a[10][10];
int b[10][10];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void dfs(int x, int y) {
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (b[nx][ny] == 0) {
b[nx][ny] = 2;
dfs(nx,ny);
}
}
}
}
int dfs() {
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
b[i][j] = a[i][j];
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (b[i][j] == 2) {
dfs(i, j);
}
}
}
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (b[i][j] == 0) {
cnt += 1;
}
}
}
return cnt;
}
int main() {
cin >> n >> m;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> a[i][j];
}
}
int ans = 0;
for (int x1=0; x1<n; x1++) {
for (int y1=0; y1<m; y1++) {
if (a[x1][y1] != 0) continue;
for (int x2=0; x2<n; x2++) {
for (int y2=0; y2<m; y2++) {
if (a[x2][y2] != 0) continue;
for (int x3=0; x3<n; x3++) {
for (int y3=0; y3<m; y3++) {
if (a[x3][y3] != 0) continue;
if (x1 == x2 && y1 == y2) continue;
if (x1 == x3 && y1 == y3) continue;
if (x2 == x3 && y2 == y3) continue;
a[x1][y1] = 1;
a[x2][y2] = 1;
a[x3][y3] = 1;
int cur = dfs();
if (ans < cur) ans = cur;
a[x1][y1] = 0;
a[x2][y2] = 0;
a[x3][y3] = 0;
}
}
}
}
}
}
cout << ans << '\n';
return 0;
}이렇게 문제 자체가 복잡하거나 조건이 까다로운 문제는 실전에서 당황하여 계속 디버깅을 해야하는 상황이 발생할 우려가 있다. 그렇기 때문에 실전처럼 시간을 정해놓고 계속 다시 풀어보는 훈련이 필요하다. 다시 풀어보면서 내가 주로 어디서 막혔는지, 어디서 계속 실수를 하는지, 사고의 과정이 어떻게 되는지를 복기하면서 스스로를 분석해야 한다.
