[BOJ][C++] 14502 연구소

[BOJ][C++] 14502 연구소

 

문제

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

 

풀이

빈 칸마다 3개의 벽을 다 세워보고 바이러스를 퍼뜨려보는 식으로 문제를 풀었습니다.

브루트포스 방식으로 풀어서 시간 초과가 날 줄 알았는데 안나더라구요.

과거에 java로 풀어본 적이 있긴 한데 그 때는 참고를 해서 풀었다면 이번에는 제 힘으로 풀어서 더 뿌듯하고 좋았습니다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;
int N, M;
int map[8][8];
int map_copy[8][8];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int max_value = 0;

void reset(int (*map1)[8], int (*map2)[8]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map1[i][j] = map2[i][j];
        }
    }
}

void Virus() {
    int virus_map[8][8];
    reset(virus_map, map_copy);
    queue<pair<int, int>> q;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (virus_map[i][j]==2) {
                q.push(make_pair(i, j));
            }
        }
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (virus_map[nx][ny] == 0) {
                virus_map[nx][ny] = 2;
                q.push(make_pair(nx, ny));
            }
        }
    }
    int res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (virus_map[i][j] == 0) {
                res+=1;
            }
        }
    }
    
    max_value = max(max_value, res);

}
void Wall(int cnt) {
    
    if (cnt == 3) {
        Virus();
        return;
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map_copy[i][j] == 0) {
                map_copy[i][j] = 1;
                Wall(cnt+1);
                map_copy[i][j] = 0;
            }
                
        }
    }
        


}
int main() {
    scanf("%d %d", &N, &M);
    for (int n = 0; n < N; n++) {
        for (int m = 0; m < M; m++) {
            scanf("%d", &map[n][m]);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                reset(map_copy, map);
                map_copy[i][j] = 1;
                Wall(1);
                map_copy[i][j] = 0;
            }
        }
    }
    printf("%d\n", max_value);
    return 0;
}