[백준 - 14502] 연구소 [C++]

1. 문제

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

14502번: 연구소

2. 풀이과정

1. 연구소의 빈 칸 3곳에 벽을 세운다.

2. 바이러스를 퍼뜨린다.

3. 안전영역의 크기를 구하고 최댓값을 갱신한다.

 

이때 벽을 세울 수 있는 모든 경우의 수에 대해 1~3을 반복한다.

[코드설명]

main함수의 3중 for문으로 벽을 세울 3곳을 선정하고,

3곳이 모두 빈 칸이면 벽을 세우고 바이러스를 퍼뜨린 후,

안전영역의 크기 계산 및 최댓값 갱신을 수행한다.

 

이때, 3곳의 좌표는

(0, 0), (0, 1), (0, 2)

(0, 0), (0, 2), (0, 3)

              .

              .

(6, 4), (6, 5), (6, 6)

순으로 선정된다.

 

또한 바이러스를 퍼뜨릴 때, 원본 지도의 데이터가 변경되는 것을 막기위해

항상 원본을 카피해서 바이러스를 퍼뜨린다.

 

dfs함수는 전달받은 지도에 바이러스를 퍼뜨려준다.

 

safe함수는 특정 좌표가 지도 영역안쪽이면 true,

지도를 벗어났으면 false를 반환해주는데 dfs함수에서 사용된다.

 

init_v함수는 visited배열을 초기화해준다.

 

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
int dy[4] = {-1, 0, 0, 1}, dx[4] = {0, -1, 1, 0};
bool visited[10][10];
int result = -1;

void init_v() {
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) visited[i][j] = false;
    }
    return;
}

bool safe(int y, int x) {
    return (0<=y && y<n) && (0<=x && x<m);
}

void dfs(int y, int x, vector<vector<int>>& v) {
    visited[y][x] = true;
    v[y][x] = 2;
    for(int i=0; i<4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(safe(ny, nx) && !visited[ny][nx] && !v[ny][nx]) {
            dfs(ny, nx, v);
        } 
    }
}

int count(vector<vector<int>>& v) {
    int cnt = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) if(!v[i][j]) cnt++;
    }
    return cnt;
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    vector<vector<int>> original(n);
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            int tmp;
            cin >> tmp;
            original[i].push_back(tmp);
        }
    }
    for(int i=0; i<n*m-2; i++) {
        for(int j=i+1; j<n*m-1; j++) {
            for(int k=j+1; k<n*m; k++) {
                if(!original[i/m][i%m] && !original[j/m][j%m] && !original[k/m][k%m]) {
                    vector<vector<int>> copy = original;
                    copy[i/m][i%m] = copy[j/m][j%m] = copy[k/m][k%m] = 1;
                    
                    for(int l=0; l<n; l++) {
                        for(int a=0; a<m; a++) {
                            if(copy[l][a] == 2 && !visited[l][a]) dfs(l, a, copy);
                        }
                    }
                    
                    result = max(count(copy), result);   
                    init_v();
                }
            }
        }
    }
    cout << result;
    return 0;
}