14502번-연구소

문제

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

14502번: 연구소

---

접근방법

1) 접근 사고

DFS + BFS 문제 였습니다.

알고리즘 과정은

1.입력값을 받고 난 board 배열에서 3개의 기둥을 설치한 뒤 

2.바이러스들이 모두 퍼집니다.(BFS 알고리즘 활용)

3.이후에 남은 공간을 측정하여 최대값일 경우 갱신합니다.

4.이때 DFS를 통해서 모든 경우를 구해주면 됩니다.

 

2) 시간 복잡도

모든 경우를 탐색해야 하므로 O(n^2)입니다.

 

3) 배운 점

무난했던 구현 문제였습니다.

 

4) PS

구현 잘해놓고 78번째 줄에서 m으로 적어야하는데 n으로 잘못적어서 시간낭비함... 논리 오류인줄 알았는데 다음부터는 조심해야겠다.

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 9;
int board[MAX][MAX];
int moveY[] = {-1,1,0,0};
int moveX[] = {0,0,-1,1};
int ret = INT_MIN;
int n, m;
 
int main(void)
{
    fastio;
 
    cin >> n >> m;
 
    for(int i =0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
        }
    }
 
    auto BFS = [&]() -> int {
        queue<pair<int,int>> q;
        int tmpboard[MAX][MAX];
        memcpy(tmpboard, board, sizeof tmpboard);
 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(tmpboard[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 + moveY[i];
                int nx = x + moveX[i];
 
                if(ny < 0 || ny >= n || nx < 0 || nx >= m)
                    continue;
                if(tmpboard[ny][nx] == 0){
                    q.push({ny, nx});
                    tmpboard[ny][nx] = 2;
                }
            }
        }
 
        int cnt = 0;
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < m; j++){
                if(tmpboard[i][j] == 0)
                    cnt++;
            }
        }
        return cnt;
    };
 
    auto DFS =[&](int cnt, auto&& DFS) -> void {
        if(cnt == 3)
        {
            ret = max(ret, BFS());
            return ;
        }
 
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 0)
                {
                    board[i][j] = 1;
                    DFS(cnt + 1, DFS);
                    board[i][j] = 0;
                }
            }
        }
    };
 
    DFS(0, DFS);
    cout <<  ret << "\n";
}