[C++] 백준 14502번: 연구소 (구현)

https://www.acmicpc.net/problem/14502

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

연구의 구조와 바이러스의 위치가 주어질 때, 벽을 세 개 세운 뒤 안전영역의 크기를 구하여라.

---

시간복잡도 어림하기

 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 구현 문제 이므로 생략하겠습니다.

---

알고리즘 설계하기

 먼저 필요한 동작을 나누어 본다면 다음과 같이 나눌 수 있습니다.

1. 벽을 세 개 세운다.
2. 바이러스를 퍼트린다.
3. 안전 영역의 크기를 구한다.

 

 가장 먼저 벽을 세 개 세우는 로직을 설계해봅시다. 벽을 세운다는 것은 원래 연구소에서 빈칸이 벽으로 바뀐다는 말입니다. 모든 빈칸 중 세 개를 선택하여 벽으로 바꿔야 하니, 전체 중 세 개를 선택하는 조합의 경우의 수와 같습니다. 연구소의 넓이가 최대 8 x 8로 64이고 64C3 = 4만 정도 되는 값입니다.

 조합 알고리즘은 어떻게 구현하면 될 까요? 일반적으로 재귀 함수를 사용하여 구현할 수 있습니다. 하지만, 이번 문제에서는 nCr에서 r의 값이 3이므로 for 루프를 세 개 중첩하여 구현합니다. nC3을 구현하는 코드는 다음과 같습니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < i; j++){
        for(int k = 0; k < j; k++){
            //서로 다른 i, j, k를 뽑음
        }
    }
}

 이렇게 전체 집합에서 세 개를 뽑는 조합은 for 루프를 중첩하여 쉽게 구현할 수 있습니다.

 

 벽을 세웠다면 바이러스를 퍼트려야 합니다. 이 문제에서는 바이러스가 어떤 순서로 퍼지는지는 중요하지 않으므로 dfs와 bfs 어느 것을 사용해도 상관없습니다. 이번 글에서는 dfs를 사용하여 구현하겠습니다.

 

 바이러스를 퍼트린 후에는 안전영역의 크기를 구해야 합니다. 안전영역의 크기는 단순하게 바이러스를 퍼트릴 때 사용한 방문처리 배열을 사용하여 방문하지 않은 위치 중 빈칸인 위치의 수를 세면 쉽게 구현할 수 있습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int a[10][10], visited[10][10], n, m, ret;
vector<pair<int, int>> virus, walls;
/*방향 배열*/
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

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 || ny >= n || nx < 0 || nx >= m) continue; //경계 체크
        if(visited[ny][nx] || a[ny][nx] == 1) continue; //방문 여부 및 벽 체크
        dfs(ny, nx);
    }
    return;
}

int solve(){
    memset(visited, 0, sizeof(visited)); //이전 방문 정보 초기화
    /*바이러스 퍼트리기*/
    for(pair<int, int> b : virus){
        dfs(b.first, b.second);
    } 

    /*안전 영역 크기 카운트*/
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 0 && !visited[i][j])cnt++;
        }
    } 
    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];
            if(a[i][j] == 2) virus.push_back({i, j});
            if(a[i][j] == 0) walls.push_back({i, j});
        }
    }
    
    for(int i = 0; i < walls.size(); i++){
        for(int j = 0; j < i; j++){
            for(int k = 0; k < j; k++){
                /*세 개의 벽 세우기*/
                a[walls[i].first][walls[i].second] = 1;
                a[walls[j].first][walls[j].second] = 1;
                a[walls[k].first][walls[k].second] = 1;
                ret = max(ret, solve());
                /*세운 벽 초기화*/
                a[walls[i].first][walls[i].second] = 0;
                a[walls[j].first][walls[j].second] = 0;
                a[walls[k].first][walls[k].second] = 0;
            }
        }
    }
    cout << ret << "\n";
    return 0;
}

 전체 순서를 살펴보면, 먼저 입력을 받으면서 바이러스의 위치와 빈칸이 위치를 각각 virus와 walls 배열에 담습니다. 이후 3중 for 루프를 통해 세울 벽을 선택하여 해당 위치를 벽으로 바꿉니다. 

 벽을 바꾸고 나면 solve 함수를 실행하여 바이러스를 퍼트리고, 안전영역의 수를 카운트 합니다. 이 과정이 모두 마무리 되면 처음 벽을 세운 위치를 다시 빈칸으로 바꿔 다음 시행에 영향을 주지 않도록 합니다.

 

 이와 같이 여러 경우의 수에 대해 결과를 구하는 문제는 초기화가 가장 중요합니다. 위 코드에서도 벽을 세운 후 다시 원상복구하는 로직이 있고, solve의 처음에 방문처리 배열 visited를 0으로 초기화하는 로직이 들어갑니다. 이처럼 초기화 로직이 들어가야 다음 시행에 영향을 미치지 않기 때문에 반드시 필요한 로직입니다.

---