BOJ 14502 : 연구소 [C++]

 

14502번: 연구소

 

 

벽을 하나씩 추가하고 3개가 추가되면 해당 상태에서 안전 구역을 BFS를 통해 얻고,

최대 안전 구역보다 크다면 갱신.

 

벽을 추가하는 과정은 재귀 함수로 구현.

벽을 추가하고 그 다음 칸부터 벽을 세워나간다.

가능한 모든 벽 추가 경우의 수를 검사할 수 있다.

 

최대 안전 구역을 얻는 함수 수행 시, 벽은 모두 방문한 것으로 처리했다.

방문하지 않은 바이러스가 있는 곳에서 BFS를 통해 감염되는 구역을 모두 방문 처리 후,

방문하지 않은 곳의 수를 세어주면 안전 구역 크기를 알 수 있다.

 

 

#include <iostream>
#include <queue>

int n = 0;
int m = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int room[9][9] = {{0, }, };
bool visited[9][9] = {{false, }, };
int max_safe_area = 0;

void bfs(int x, int y) {
    std::queue<std::pair<int, int>> trace;
    trace.push({x, y});
    visited[x][y] = true;

    while (!trace.empty()) {
        int cur_x = trace.front().first;
        int cur_y = trace.front().second;
        trace.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur_x + dx[i];
            int ny = cur_y + dy[i];

            if (nx < 1 || nx > n || ny < 1 || ny > m) {
                continue;
            }
            if (visited[nx][ny] == false) {
                trace.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
    }
}

int get_safe_area() {
	// 벽은 모두 방문 처리
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            if (room[i][j] == 1) {
                visited[i][j] = true;
            } else {
                visited[i][j] = false;
            }
        }
    }
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            if (room[i][j] == 2 && visited[i][j] == false) {
                bfs(i, j);
            }
        }
    }
    // 방문하지 않은 곳의 수를 세어준다.
    int ret = 0;
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            if (visited[i][j] == false) {
                ret++;
            }
        }
    }
    return ret;
}

void sol(int x, int y, int num_of_wall) {
    for (int i = x; i < n + 1; i++) {
        int j = 1;
        if (i == x) {
            j = y;
        }
        for (; j < m + 1; j++) {
        	// 빈칸이면 벽을 세우고, 다음 칸을 세우기 위해 다시 sol 호출
            // 세 개의 벽을 모두 세웠다면 get_safe_area를 통해 안전 구역 크기를 얻는다
            if (room[i][j] == 0) {
                room[i][j] = 1;
                if (num_of_wall == 3) {
                    int safe_area = get_safe_area();
                    if (safe_area > max_safe_area) {
                        max_safe_area = safe_area;
                    }
                } else {
                    sol(i, j + 1, num_of_wall + 1);
                }
                room[i][j] = 0;
            }
        }
    }
}

int main() {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            room[i][j] = 0;
        }
    }

    std::cin >> n >> m;

    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            std::cin >> room[i][j];
        }
    }

    sol(1, 1, 1);

    std::cout << max_safe_area << "\n";

    return 0;
}