[BOJ/14502번연구소] c++/ BFS

문제

연구소에 벽 세개를 세워 확산되는 바이러스로부터 안전 영역의 최대 크기를 구하는 문제

바이러스는 벽을 통과할 수 없음

-빈칸은 0, 벽은 1, 바이러스는 2로 표시

 

생각

연구소에 벽 3개를 세워야 하는데,

세로, 가로 크기가 최대 8인걸 보고 브루트포스 문제라고 생각함

근데 구현을 못함. 그래서 구글링함 김재현이 이해도와줌

 

문제풀이

1. 벽 세개를 세우기 전에, 처음 입력받은 연구소 배열을 복사해둠

2.반복문 사용해서 벽 세개를 세움

-재귀 사용

-재귀의 베이스 조건이 cnt = 0 일 때, 벽 3개를 세운 배열을 BFS 탐색함

-백트래킹 (공부해야함)

3.BFS 돌려서 빈칸 개수 세고, 최댓값 구함

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[9][9], board2[9][9];
int vis[9][9];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N, M, cnt=3, Max=0;
void BFS();
void Cnt();
void wall() {
    if ( cnt == 0 )
        return BFS();

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( board2[i][j] == 0 ) {
                cnt--;
                board2[i][j] = 1;
                wall();
                cnt++;
                board2[i][j] = 0;    
            }
        }
    }
}
void BFS() {
    for ( int i = 0; i < N; i++ ) 
        for ( int j = 0; j < M; j++ ) {
            board[i][j] = board2[i][j];
            vis[i][j] = 0;
        }
            
    queue<pair<int, int>> Q;
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( board[i][j] == 1 )
                vis[i][j] = 1;

            else if ( board[i][j] == 2 ) {
                Q.push({i, j});
                vis[i][j] = 1;
            }
        }
    }

    while (!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();

        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            if ( board[nx][ny] != 0 || vis[nx][ny] ) continue;

            board[nx][ny] = 2;
            vis[nx][ny] = 1;
            Q.push({nx, ny});
        }
    }
    
    Cnt();
}
void Cnt() {
    int c = 0;
    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < M; j++ )
            if ( board[i][j] == 0 )
                c++;
    
    Max = max(c, Max);
}

int main() {
    ios::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 >> board2[i][j];
        
    wall();
    cout << Max;
    
}