BOJ 14502 - 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

조합탐색 + BFS 를 사용해서 풀어야 하는 문제이다.

 

브루트포스 사용시에 활용되는 조합과 순열에 대한 설명은 아래 블로그를 참조바란다

yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

 

먼저 주어진 맵에서 0의 총 갯수 중 3개를 선택하여 그 3개를 벽으로 만들어야 하며 (1로 변환)

n 개 중 3 개를 뽑는 것 이므로 조합을 이용해서 뽑아낸다. (아래 코드의 함수 void build_wall(int idx, int wall))

3개를 뽑는 것을 구현하기 위해 bool checked[MAX * MAX]; 라는 일차원 전역 변수를 만들고 

true 면 뽑은 것, false 면 안뽑은 것으로 처리하여 조합을 구현한다.

 

3개를 다 뽑았으면 바이러스를 퍼트리고, 남은 0의 갯수를 구할 함수를 만든다 (아래 코드의 함수 void spread())

n 개 중 3개를 뽑을때 마다, 바이러스를 퍼트리는 시뮬레이션을 해야 하므로, 

기존 맵의 복사본을 만들고, 방문여부를 나타내는 visited 배열을 초기화한다.

그 후 방문 처리된 0 의 값의 좌표를 구하기 위해 반복문을 돌려 3개를 찾아내고 그 좌표들의 값을 1로 만든다

(벽을 세웠다는 의미)

그리고 각각의 바이러스 좌표들을 이용해서 bfs 를 수행한다. (바이러스 퍼트리는 용도)

이후, 남아있는 0의 갯수를 확인한다.

 

 

- c++

 

#include <bits/stdc++.h>
 
#define MAX 8 
 
using namespace std;
 
int n, m, answer, zero_cnt;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int adj[MAX][MAX];
int copy_adj[MAX][MAX];
bool visited[MAX][MAX];
bool checked[MAX * MAX];
vector<pair<int, int>> virus, zero;
 
void copy_map() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            copy_adj[i][j] = adj[i][j];
        }
    }
}
 
int count_zero() {
    int cnt = 0;
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < m; ++j) 
            if (copy_adj[i][j] == 0) cnt++;
    return cnt;
}
 
void bfs(int y, int x) {
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    visited[y][x] = true;
    
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        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] && copy_adj[ny][nx] == 0) {
                visited[ny][nx] = true;
                q.push(make_pair(ny, nx));
                copy_adj[ny][nx] = 2;
            }
        }
    }
}
 
void spread() {
    int cnt = 0;
    
    copy_map();
    memset(visited, false, sizeof(visited));
    
    for (int i = 0; i < zero_cnt; ++i) {
        if (cnt == 3) break;
        if (checked[i]) {
            int y = zero[i].first;
            int x = zero[i].second;
            copy_adj[y][x] = 1;
            cnt++;
        }
    }
    
    for (int i = 0; i < virus.size(); ++i) {
        int y = virus[i].first;
        int x = virus[i].second;
        bfs(y, x);
    }
    
    answer = max(answer, count_zero());
}
 
void build_wall(int idx, int wall) {
    if (wall == 3) {
        spread();
        return;
    }
    
    for (int i = idx; i < zero_cnt; ++i) {
        if (checked[i]) continue;
        checked[i] = true;
        build_wall(i, wall + 1);
        checked[i] = false;
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> adj[i][j];
            if (adj[i][j] == 0) zero.push_back(make_pair(i, j));
            if (adj[i][j] == 2) virus.push_back(make_pair(i, j));
        } 
    } 
    zero_cnt = zero.size();
    
    build_wall(0, 0);
    
    cout << answer;
    
    return 0;
}