[BOJ 14502] 연구소

문제 요약

• N×M 격자에 벽 3개 세워서 바이러스 확산 막기
• (이미 벽도 좀 세워져 있음)
• 안전 영역 최대화

접근

빈 칸 중 3개 골라서 벽 세우고 BFS로 바이러스 퍼뜨린 뒤 안전 영역 계산. 경우의 수가 크지 않아서 브루트포스로 충분했음.

3 <= N, M <= 8 : 범위

핵심 로직

• 빈 칸 목록 따로 저장해두고 3중 for문으로 조합
• 매 조합마다 grid 복사해서 BFS
• 안전 영역 = 전체 - 벽(초기 + 3) - 바이러스(초기+확산)

실수 or 배운 점

• 거의 다 했는데 3개 조합 뽑는게 애매했다. 결국 빈칸좌표를 미리 vector에 저장해서 뽑으니까 깔끔했고, 백트래킹까지 하니까 보기 좋더라.

코드

// Online C++ Compiler - Build, Compile and Run your C++ programs online in your favorite browser
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N, M;
    int maxArea = 0;
    cin >> N >> M;
    vector<vector<int>> arr(N, vector<int>(M, 0));
    vector<pair<int, int>> v;
    vector<pair<int, int>> e;
    int wallCnt = 0;
    int vCnt = 0;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            int temp;
            cin >> temp;
            arr[i][j] = temp;
            if(temp == 2){
                v.push_back({i,j});
                vCnt++;
            }
            else if(temp == 1) wallCnt++;
            else{
                e.push_back({i, j});
            }
        }
    }
    
    
    
    
    int K = e.size();
    //pick 3
    for (int i = 0; i < K; ++i) {
        for (int j = i + 1; j < K; ++j) {
            for (int k = j + 1; k < K; ++k) {
                // wall
                arr[e[i].first][e[i].second] = 1;
                arr[e[j].first][e[j].second] = 1;
                arr[e[k].first][e[k].second] = 1;
    
                
    
                queue<pair<int, int>> q;
                int vCnt2 = 0;
                for(auto vv : v){
                    q.push(vv);
                }
                auto tempArr = arr;
                //start spread
                while(!q.empty()){
                    auto [y, x] = q.front(); q.pop();
                    int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1};
                    
                    for(int m = 0; m < 4; m++){
                        int ny = y + dy[m]; int nx = x + dx[m];
                        if(0 <= nx && nx < M && 0 <= ny && ny < N && tempArr[ny][nx] != 2 && tempArr[ny][nx] != 1) {
                            q.push({ny, nx});
                            tempArr[ny][nx] = 2;
                            vCnt2++;
                        }
                    }
                    
                }
                
                maxArea = max((N*M - (wallCnt+3) - (vCnt+vCnt2)), maxArea);
                // fuck wall
                arr[e[i].first][e[i].second] = 0;
                arr[e[j].first][e[j].second] = 0;
                arr[e[k].first][e[k].second] = 0;
            }
        }
    }
    
    cout << maxArea;
   
    
    
    
    return 0;
}