[BOJ] 14502번 | 연구소 (C++)

🔗문제 보러가기

14502번: 연구소

 

🧑‍💻풀이 과정

 

연구소의 크기가 최대 \(8 \times 8\) 이기 때문에 벽을 3개 설치하는 모든 경우의 수에 대해 탐색하여 풀었습니다. 백트래킹과 BFS 탐색을 잘 구현하는 것이 목표인 문제인 것 같네요.

 

1. 2차원 배열에 연구소 정보를 입력 받고, 바이러스의 위치 정보도 별도의 배열에 저장한다.
2. 조합(Combination) 방식을 이용해 열 방향 순서로 벽 3개를 설치한다.
   • 빈 공간일 때에만 벽을 설치한다.
   • 벽을 3개 설치 다 했다면, 3번 과정을 진행 후 백트래킹을 통해 되돌아간다.
3. 벽 3개가 다 설치됐다면, BFS 탐색을 통해 바이러스 잠식 시뮬레이션을 시작한다.
   • 이 때 스택(Stack)을 별도로 두어, 여기에 바이러스가 다녀갔던 위치들을 넣어둔다.
   • 바이러스 잠식 시뮬레이션이 끝났다면, 연구소 전체를 순회하며 안전 지역 개수를 체크한다.
   • 안전 지역 개수 체크가 끝났다면, 스택이 빌 때까지 pop() 하며 바이러스가 잠식한 공간을 다시 빈 공간으로 되돌린다.
   • 안전 지역 개수를 저장하는 변수에 대해, 더 큰 값으로 갱신한다.
4. 2 ~ 3번 과정을 연구소 전체 맵에 대해 진행한다.

 

✏️ 소스 코드 및 결과

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
using Matrix = vector<vector<int>>;
using Position = pair<int, int>;

#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define EMPTY 0
#define WALL 1
#define VIRUS 2
#define MAX_WALL_COUNT 3

vector<vector<int>> Directions { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
vector<Position> VirusPositions;
int N, M;


int GetSafeArea(const Matrix& field) {
    int area = 0;
    for (const auto& line : field) {
        for (const auto& element : line) {
            if (element == EMPTY)
                area++;
        }
    }

    return area;
}

int BFS(Matrix& field) {
    queue<Position> positions;
    for (const auto& virusPos : VirusPositions)
        positions.emplace(virusPos.first, virusPos.second);

    stack<Position> back;
    while (!positions.empty()) {
        int currentRow = positions.front().first;
        int currentCol = positions.front().second;
        positions.pop();

        for (const auto& direction : Directions) {
            int nextRow = currentRow + direction[0];
            int nextCol = currentCol + direction[1];

            if (nextRow < 0 or nextRow >= N or nextCol < 0 or nextCol >= M)
                continue;
            if (field[nextRow][nextCol] != EMPTY)
                continue;
            
            field[nextRow][nextCol] = VIRUS;
            positions.emplace(nextRow, nextCol);
            back.emplace(nextRow, nextCol);
        }
    }

    int safeArea = GetSafeArea(field);

    while (!back.empty()) {
        int row = back.top().first;
        int col = back.top().second;
        
        back.pop();
        field[row][col] = EMPTY;
    }

    return safeArea;
}

void BackTracking(Matrix& field, vector<Position>& newWalls, int& safeArea, int row, int col) {
    if (newWalls.size() == MAX_WALL_COUNT) {
        int newResult = BFS(field);
        safeArea = max(safeArea, newResult);
        return;
    }

    int c;
    for (int r = row; r < N; r++) {
        // 열이 바뀌면 다시 열 초기화
        c = (c >= M) ? 0 : col;
        for (; c < M; c++) {
            if (field[r][c] == WALL or field[r][c] == VIRUS)
                continue;
            
            field[r][c] = WALL;
            newWalls.emplace_back(r, c);

            BackTracking(field, newWalls, safeArea, r, c + 1);

            field[r][c] = EMPTY;
            newWalls.pop_back();
        }
    }
}

int StartSimulation(Matrix& field) {
    int safeArea = 0;
    vector<Position> newWallPositions;

    BackTracking(field, newWallPositions, safeArea, 0, 0);
    return safeArea;
} 

int main() {
    FAST_IO
    cin >> N >> M;

    Matrix field(N, vector<int>(M));
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < M; col++) {
            cin >> field[row][col];

            if (field[row][col] == VIRUS)
                VirusPositions.emplace_back(row, col);
        }
    }
    
    int answer = StartSimulation(field);
    cout << answer;

    return 0;
}