[백준 14502번 C/C++] 연구소

[백준 14502번 C/C++] 연구소

 

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

14502번: 연구소

---

 

 

해결전략

 

구현, 브루트 포스 Brute Force

너비우선탐색 BFS

 

---

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dirY[4] = { -1, 0, 1, 0 }; 
int dirX[4] = { 0, -1, 0, 1 }; 

int n, m; // n: 세로 길이, m: 가로 길이
int safe; // 안전 영역의 최대 크기(결과로 구하는 값)

vector<vector<int>> map, v; // map: 초기 지도, v: 벽을 세운 후의 지도
vector<pair<int, int>> zero, one, two; // zero: 빈 공간의 좌표, one: 벽의 좌표, two: 바이러스의 좌표
queue<pair<int, int>> Qtwo; // 바이러스의 좌표를 담는 큐
vector<vector<int>> visited; // 해당 좌표를 방문했는지 여부를 저장하는 2차원 벡터
vector<vector<int>> ch; // 바이러스가 퍼지는 과정을 저장하는 2차원 벡터
vector<bool> Select; // 벽을 세울 위치를 선택했는지 여부를 저장하는 벡터

// 바이러스가 퍼지는 과정을 계산하는 함수
void Calculate()
{
    queue<pair<int, int>> Q;
    Q = Qtwo;
    ch = visited;

    vector<vector<int>> temp = v; // 현재 지도를 복사하여 사용

    while (!Q.empty())
    {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dirY[i];
            int nx = x + dirX[i];

            if (ny < 0 || n <= ny || nx < 0 || m <= nx || temp[ny][nx] != 0) continue;

            if (ch[ny][nx] == 0)
            {
                temp[ny][nx] = 2; // 바이러스를 퍼뜨림
                ch[ny][nx] = 1; // 해당 좌표를 방문했음을 표시
                Q.push({ ny, nx });
            }
        }
    }

    int cnt = 0;
    for (int y = 0; y < n; y++){
        for (int x = 0; x < m; x++){
            if (temp[y][x] == 0) cnt++; // 안전 영역인 경우 카운트 증가
        }
    }

    safe = max(safe, cnt); // 현재까지의 안전 영역 크기와 비교하여 최대값 갱신

    v = map; // 벽을 세운 후의 지도를 초기 상태로 복구
}

// 벽을 세우는 모든 경우를 탐색하는 함수 (0인곳 중에 3개를 고르는 경우의 수)
void Combination(int idx, int cnt) // nC3
{
    if (cnt == 3) { // 벽을 3개 세운 경우
        Calculate(); // 바이러스가 퍼지는 과정 계산
        return;
    }

    for (int i = idx; i < zero.size(); i++)
    {
        if (Select[i] == false)
        {
            Select[i] = true;
            v[zero[i].first][zero[i].second] = 1; // 벽을 세움
            Combination(i + 1, cnt + 1); // 다음 위치에 벽을 세우기 위해 재귀 호출
            v[zero[i].first][zero[i].second] = 0; // 벽을 다시 제거하여 다른 경우를 탐색
            Select[i] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m; 
    map.resize(n, vector<int>(m)); 	// 초기 지도 크기 설정
    v.resize(n, vector<int>(m)); 	// 벽을 세운 후의 지도 크기 설정
    visited.resize(n, vector<int>(m, 0)); // 방문 여부를 나타내는 2차원 벡터 크기 설정
    ch.resize(n, vector<int>(m, 0)); // 바이러스 퍼짐 여부를 나타내는 2차원 벡터 크기 설정
    Select.resize(n * m, false); // 벽을 세울 위치 선택 여부를 나타내는 벡터 크기 설정
    for(int y = 0; y < n; y++){
        for (int x = 0; x < m; x++) {
            cin >> v[y][x]; 
            map[y][x] = v[y][x]; // 초기 지도에도 복사

            if (v[y][x] == 0) 
                zero.push_back({ y, x }); // 빈 공간인 경우 zero 벡터에 좌표 저장
            else if (v[y][x] == 2){
                Qtwo.push({ y, x }); // 바이러스인 경우 바이러스 큐에 좌표 저장
                visited[y][x] = 1; // 해당 좌표를 방문했음을 표시
            } 
        }
    }

    Combination(0, 0); // 벽을 세우는 모든 경우 탐색

    cout << safe << "\n"; // 안전 영역의 최대 크기 출력

    return 0;
}

 

 

---