연구소

문제: 연구소 (백준 14502번)

구조 분석

해당 문제는 두 가지 큰 알고리즘이 합쳐진 문제이다. 문제의 제시문을 보고 아래의 알고리즘 유추를 할 수 있다.

1. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
   • 이는 전형적인 BFS 문제이다.
   • BFS는 Queue임을 기억하자.
2. 새로 세울 수 있는 벽의 수는 3개이며, 꼭 3개를 세워야 한다.
   • 이는 주어진 지도에서 벽을 3개를 세우는 경우의 수를 따지는 문제이다.
   • Brute force를 이용하여 벽을 3개를 세우자.

정리해보면 다음과 같다. 우선 Brute force를 이용하여 벽을 3개를 세우고 각각의 경우에 대해서 BFS를 이용하여 바이러스가 퍼지는 상황을 만든 뒤 0으로 채워진 블록 수를 구하면 된다.

풀이 방법

이는 처음에 접했을 때, 2개의 카테고리가 혼합된 형태여서 매우 당황스러웠고, 반복문을 작성하다보니 “내가 하는 방식이 맞나?”라는 의심이 계속 들었다. 그러나 이러한 문제에 당황하지 않고 각각의 카테고리를 논리적으로 적용시키며 순서대로 풀면 된다.

우선 Brute force를 이용하기 위해 반복문을 작성하자. 이중 for문을 이용하여 지도를 순회하면서 0인 칸을 1로 고치면 벽을 세우는 것이다. 벽을 3개를 세우기 위해서는 이중 for문을 총 3번 순회해야한다. Brute force를 이용하기로 했으면 쫄지 말자!

다음으로 BFS를 이용하기 위해 bfs용 함수를 따로 만들어서 2인 바이러스 칸을 만나면 queue에 넣는다. 이후 Queue에서 하나씩 꺼내면서 expand를 실시한다.

이때, 이를 편하게 하기 위해서 상하좌우를 탐색할 수 있는 배열 dx = {-1,1,0,0}과 dy = {0,0,-1,1}을 이용하면 더 깔끔하게 탐색을 실시할 수 있다.

또한 pair를 이용해 queue를 사용하면 더 편리하다. Queue에 넣을 때, 지도의 x좌표와 y좌표를 같이 넣기 위해서 queue<pair<int,int>> Q;를 이용하여 생성하고, push를 실시할 때에도, Q.push(make_pair(i,j));로 push를 실시하면 된다.

코드

#include <stdio.h>
#include <iostream>
#include <queue>
#define MAX(a,b) (a>b?a:b)
using namespace std;

int n, m;
int c = 0;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int map[8][8];
int tmp[8][8];
int spd[8][8];

void copyMap(int map[8][8], int tmp[8][8]) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            tmp[i][j] = map[i][j];
        }
    }
}

void bfs() {
    queue<pair<int,int>> Q;
    copyMap(tmp,spd);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (spd[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 i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0<=nx && nx<n && 0<=ny && ny<m) {
                if (spd[nx][ny] == 0) {
                    spd[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 (spd[i][j] == 0) {
                cnt++;
            }
        }
    }
    c = MAX(c, cnt);
}

int main() {
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> map[i][j];
        }
    }
    for (int i1=0; i1<n; i1++) {
        for (int j1=0; j1<m; j1++) {
            copyMap(map, tmp);
            if (tmp[i1][j1]==0) {
                tmp[i1][j1] = 1;
                for (int i2=0; i2<n; i2++) {
                    for (int j2=0; j2<m; j2++) {
                        if (tmp[i2][j2]==0) {
                            tmp[i2][j2] = 1;
                            for (int i3=0; i3<n; i3++) {
                                for (int j3=0; j3<m; j3++) {
                                    if (tmp[i3][j3]==0) {
                                        tmp[i3][j3] = 1;
                                        bfs();
                                        tmp[i3][j3] = 0;
                                    }
                                }
                            }
                            tmp[i2][j2] = 0;
                        }
                    }
                }
                tmp[i1][j1] = 0;
            }
            
        }
    }
    cout << c << "\n";
    return 0;
}  

정리

해당 문제는 처음 접했을 떄 매우 당황스러웠던 문제이다. 이전에 풀던 문제보다 풀이도 더 길고 조금 더 복잡하여 풀면서 계속해서 의심이 들었다. 그러나 이러한 문제에 쫄지 말고 제시문을 잘 분석하여 구조를 파악하고 시작한다면 확신을 가지고 풀 수 있을 것이다.