[그래프 / BOJ 14502 / C++] 연구소

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

14502번: 연구소

1) 순서와 상관없이 빈공간 중에서 3개를 뽑는다.
2) 앞에서 구한 경우의 수만큼 반복문을 돌려준다. 
2-1) 벽을 세워준다.
2-2)모든  바이러스를 확산(dfs) 시킨다.
2-3) 안전구역의 개수를 구한다.
2-4) 안전구역이 최대값인지 확인한다.
3) 안전 구역의 최대값을 출력한다.

일단 전체 범위를 보면 그렇게 크지 않다. 즉, 그냥 문제 설명대로 따라가기만 해도 문제가 풀린다!

 

무식하게 한번해보자.

 

 

우선, 벽을 세울 3개의 공간을 골라야한다. 그런데, 총 빈칸의 개수 중에서 벽을 세울 공간 3개를 구해야한다.

즉, 조합을 의미한다.

 

<1>

순서없이 3가지를 뽑는 경우를 구하면 된다. 이는 3중 for문으로 구현 가능하다. 

 

<2>

그 다음으로는 벽을 세웠으니, 벽을 세우고 난 다음 virus들의 위치에서 dfs를 시작한다!

 

virus를 확산(dfs)를 시킨 다음, 배열의 크기만큼 (NxM) 순회하면서 

  1) 아직 빈 공간(0)인지,

  2) 아직 바이러스가 방문을 안했는지,

를 확인한다. 만약 이 조건이 충족되면 safe area이다!

 

<3>

이렇게 safe area의 개수를 모두 세주면, 이 값이 최대값인지 확인한다!

 

<1>,<2>,<3> 과정을 3개의 벽을 뽑는 경우의 수만큼 반복하면 벽을 어디에 세울 때 안전구역이 가장 많이 나오는지 구할 수 있다!

 

논리는 간단한데, vis 배열의 초기화와 배열의 크기를 계속 잘못설정했다,, NxM이 아님을 인지하자.

특히 2차원 배열 초기화는 fill(&a[0][0], &a[0][0] + 100*100, -1) 처럼 fill 함수를 사용해주자!

#include <bits/stdc++.h>

using namespace std;

int N, M, res;

int board[10][10], vis[10][10];
vector<pair<int,int>> blanks; // 빈칸 좌표 모아둠
vector<pair<int,int>> virus; // 바이러스 좌표 모아둠

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    
    
    for(int i=0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if(ny >= N || nx >= M || ny < 0 || nx < 0) continue;
        if(vis[ny][nx]==1 || board[ny][nx]==1) continue;
   
        vis[ny][nx]=1; // 방문표시
        dfs(ny, nx);
    }
    
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    
    cin >> N >> M;
    
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            cin >> board[i][j];
            if(board[i][j]==0) blanks.push_back({i,j});
            if(board[i][j]==2) virus.push_back({i,j});
            
        }
    } // 입력 받고 & 빈칸 좌표 저장
    

    
    for(int i = 0 ; i < blanks.size() ; i++){
        for(int j = 0 ; j < i ; j++){
            for(int k = 0 ; k < j ; k++){
                
                board[blanks[i].first][blanks[i].second] = 1;
                board[blanks[j].first][blanks[j].second] = 1;
                board[blanks[k].first][blanks[k].second] = 1; // 벽세우기
                
                fill(&vis[0][0], &vis[0][0] + 10*10, 0); //2차원 배열 초기화
                
                for(auto k : virus) {
                    vis[k.first][k.second] = 1; // 첫번째 방문
                    dfs(k.first, k.second);
                } // 바이러스 개수만큼 dfs
                
                int safe_area=0;
                
                for(int l = 0 ; l < N ; l++){
                    for(int m = 0; m < M ; m++){
                        if(board[l][m]==0 && !vis[l][m]) safe_area++; // board==0이고 vis==0이면 safe_area
                    }
                }
                
                res = max(safe_area, res); // 최댓값 갱신
                
                board[blanks[i].first][blanks[i].second] = 0;
                board[blanks[j].first][blanks[j].second] = 0;
                board[blanks[k].first][blanks[k].second] = 0; // 세웠던데 다시 치우기
                
            }
        }
    } // 빈칸 중에 3개 뽑기
    
    
        
        
    
    
    
    
    cout << res;
    
}