[BOJ] - 14502. 연구소

[URL]

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

14502번: 연구소

 

[풀이 과정]

* DFS, BFS

 

1. map입력 : 0인 곳 저장(빈공간),  2인 곳 저장(바이러스) --> 벡터에 저장

 

2. 빈 공간 중 후보군 3개 선출(DFS)

 

3. 3개 선출 한 곳 벽으로 세우고 바이러스 확산(BFS)

 

4. 최종 빈 공간 계산 --> 최대치 계산

 

[소스 코드]

 

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
 
struct info {
    int x;
    int y;
};
 
int N, M;
int map[8][8];
int c_map[8][8];
int MAX;
 
vector <info> v;
vector <info> virus;
 
bool checkDFS[64];    // DFS에서 체크 배열
bool checkBFS[8][8] = {0, };
int candIndex[3];    // v값들 중 3개 후보 인덱스!! 저장
 
queue <info> q;
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
 
void clear() {
    memset(checkDFS, 0, sizeof(bool) * 64);
    memset(candIndex, -1, sizeof(int) * 3);
}
 
void input() {
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
 
            // 빈 공간 벡터에 담기
            if (map[i][j] == 0)
            {
                info temp;
                temp.x = i;
                temp.y = j;
 
                v.push_back(temp);
            }
 
            // 바이러스 벡터에 담기
            if (map[i][j] == 2)
            {
                info temp;
                temp.x = i;
                temp.y = j;
 
                virus.push_back(temp);
            }
        }
    }
}
 
void BFS(int index) {
    info temp;
    temp.x = virus[index].x;
    temp.y = virus[index].y;
 
    q.push(temp);
 
    while (!q.empty())
    {
        int cx = q.front().x;
        int cy = q.front().y;
        checkBFS[cx][cy] = true;
 
        q.pop();
 
        for (int k = 0; k < 4; k++)
        {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
 
            if (nx >= 0 && nx < N &&  ny >= 0 && ny < M && c_map[nx][ny] == 0 && checkBFS[nx][ny] == false)
            {
                c_map[nx][ny] = 2;
 
                info temp;
                temp.x = nx;
                temp.y = ny;
 
                q.push(temp);
            }
        }
    }
}
 
// 벽 세워 놓고 바이러스 퍼졌을 때 나오는 빈공간 계산
int calc() {
    int res = 0;
 
    // map[][] --> c_map[][] 카피
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            c_map[i][j] = map[i][j];
        }
    }
 
    // 후보 3개 벽으로 넣어주기
    for (int i = 0; i < 3; i++)
    {
        c_map[v[candIndex[i]].x][v[candIndex[i]].y] = 1;
    }
 
    // check[][] 0으로 초기화
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            checkBFS[i][j] = 0;
        }
    }
 
    // 바이러스 확산
    for (int i = 0; i < virus.size(); i++)
    {
        BFS(i);
    }
 
    // 최종 남은 공간 계산
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (c_map[i][j] == 0)
            {
                res++;
            }
        }
    }
 
    return res;
}
 
void DFS(int cnt) {
    if (cnt == 3)
    {
        // 후보 3개 추출
        int temp = calc();
        if (temp > MAX)
            MAX = temp;
 
        return;
    }
 
    //개념: 가능한 후보 전체(v.size()) 중 3개만 추출
    for (int i = candIndex[cnt - 1]; i < v.size(); i++)
    {
        if (candIndex[cnt] == -1 && checkDFS[i] == false)
        {
            checkDFS[i] = true;
            candIndex[cnt] = i;
 
            DFS(cnt + 1);
 
            candIndex[cnt] = -1;
            checkDFS[i] = false;
        }
    }
}
 
int main() {
 
    //clear();
    clear();
 
    // 1. 맵 입력
    input();
 
    // 2. dfs() -> 벽 3개 정하기
    DFS(0);
 
    printf("%d\n", MAX);
 
    return 0;
}