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

문제링크 : https://www.acmicpc.net/problem/14502

14502번: 연구소

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, result = 0;
int arr[8][8]; //원본
int arr2[8][8]; //감염
int wall[8][8]; //벽
int dx[] = {1, -1, 0 , 0};
int dy[] = {0, 0, 1, -1};

void bfs()
{
    memcpy(arr2, wall, sizeof(wall)); //벽이 세워진 상태에서 감염를 위한 배열 복사
    queue<pii>q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if(arr2[i][j]==2) q.push({i,j}); //감염 위치 큐에 추가
        }
    }

    while(!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(nx < 0 || ny < 0 || ny>=N || nx>=M) continue; //범위 체크
            if(arr2[ny][nx]) continue; //추가 감염가능 여부 체크
            q.push({ny, nx});
            arr2[ny][nx]=2; //감염
        }
    }

    int cnt = 0;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(!arr2[i][j]) cnt++; //최대 안전영역 카운팅
        }
    }
    result = max(cnt, result);
}

void func(int cnt) //벽 3개 세우기
{
    if(cnt==3) return bfs();

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(!wall[i][j]) //벽 가능여부 체크
            {
                wall[i][j] = 1;
                func(cnt+1); //벽 추가
                wall[i][j] = 0; //다른 케이스 체크를 위해 초기화
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin >> arr[i][j];
        }
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(!arr[i][j]) //0이면 벽세우기 가능
            {
                memcpy(wall, arr, sizeof(arr)); //벽을 세울 배열 복사
                wall[i][j]=1; //현재 위치에 대해 벽 추가 (최초벽)
                func(1); //벽 3개 체크
            }
        }
    }

    cout << result;

    return 0;
}

브루트포스와 bfs로 푼 문제이다.

해당 문제에 배열이 다음과 같이 총 3개가 필요하다.

- 원본 배열

- 위 배열에 벽이 세워진 배열

- 위 배열에 감염이 추가된 배열

 

그렇기에 배열 복사가 여러번 이루어진다.

 

먼저 벽을 세워야 하므로 원본 배열을 먼저 복사하여 가져온다.

그리고 현재 값이 0일때 벽을 세우는 것이 가능하므로 최종 벽 갯수인 3개가 될때까지 벽을 세워준다.

이때 다른 케이스가 존재할 수 있으므로 세웠던 벽은 다시 치워주는 것도 해주어야 한다.

벽 3개를 모두 골랐다면 이제 bfs 탐색을 돌린다.

 

이제 여기서 감염된 부분 및 안전 구역을 구해준다.

먼저 벽이 세워진 상태에서 감염이 얼마나 이루어지는 지를 봐야하기 때문에 또 배열 복사를 해준다.

그리고 해당 배열의 최초 감염 위치를 토대로 탐색을 시작하며, 추가적인 감염가능 여부를 확인하고 감염을 진행한다.

감염을 모두 진행했다면 이제 해당 배열을 토대로 안전영역을 카운팅해주고 해당 값이 가장 클 때를 저장하고 출력해주면 된다.

 

요약하자면 다음과 같다.

1. 최초 가능한 위치에 벽 세움 (메인문)

2. 1번 벽 위치 기준으로  2개까지 벽 추가 건설 (func 함수)

3. 3개가 건설된 상태로 감염 진행  (bfs 함수)

4. 감염 진행후 안전영역체크 (bfs 함수)

5. 1번 위치 이후 벽 세우기가 가능한 위치에서 1~4번 반복