[ 백준 14502 ] 연구소 (C++) - BFS

---

🔗 문제 링크

14502번: 연구소

---

💡 문제 풀이 및 해석

먼저 가로, 세로 조건이 8이하이다. 따라서 전체 칸은 64칸이다. 3개의 모든 기둥을 박아야 하므로 64개의 칸 중에서 3개를 선택하는 조합, 그리고 그 상태에서 BFS를 진행한다고 하면, 최대 $64\times63\times62\over3\times2\times1$ $\times64 = 2,666,496$ 이 된다. 이를 토대로 완전탐색을 진행하기로 하였다.

1. 먼저 64개의 칸중 3개의 칸을 조합으로 구성한다.
2. 그 구성이 실제로 가능하면 (벽이 있거나, 감염된 칸이 아니라면) 감염(BFS)을 시켜본다.
3. 감염이 끝난 후에 살아남은 칸을 구해서 가장 큰 값을 출력한다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define endl "\n"
using namespace std;

int N, M;
int MAP[8][8];
int answer = 0;
int next_x[] = { -1,1,0,0 };
int next_y[] = { 0,0,1,-1 };
vector<vector<int>> Batch;
queue<pair<int,int>> q;
void input() {
    cin >> N >> M;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            cin >> MAP[y][x];
            if (MAP[y][x] == 2) {
                q.push({ x,y });
            }
        }
    }
}
void reMap(int (&Map)[8][8]) {
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            Map[y][x] = MAP[y][x];
        }
    }
}
void Test() {
    int Map[8][8] = { 0 };
    queue<pair<int, int>> virus;
    // 모든 배치 탐색
    for (int i = 0; i < Batch.size(); i++) {
        reMap(Map); // 배치마다 리셋
        for (int j = 0; j < Batch[i].size(); j++) {
            // 어디에 있는 기둥인지 확인
            int Y = Batch[i][j] / M;
            Batch[i][j] %= M;
            int X = Batch[i][j];

            if (Map[Y][X] != 0) break; // 기둥을 세울 수 없는 배치면 PASS
            else Map[Y][X] = 1; // 기둥을 세움

            if (j == 2) {
                virus = q; // 매번 리셋
                while (!virus.empty()) {
                    int x = virus.front().first, y = virus.front().second; virus.pop();
                    for (int k = 0; k < 4; k++) {
                        int nx = x + next_x[k], ny = y + next_y[k];
                        if (nx > -1 && ny > -1 && nx < M && ny < N) { // 범위 안이고
                            if (Map[ny][nx] == 0) { // 감염될 수 있는 칸이라면
                                virus.push({ nx,ny });
                                Map[ny][nx] = 2;
                            }
                        }
                    }
                }
                int ans = 0;
                for (int y = 0; y < N; y++) {
                    for (int x = 0; x < M; x++) {
                        if (Map[y][x] == 0) ans++;
                    }
                }
                answer = max(answer, ans);
            }
        }
    }
}

void batch() {
    vector<int> s;
    vector<int> temp{ 1,1,1 }; // 기둥 3개를 박아야함

    for (int i = 0; i < N * M; i++) {
        s.push_back(i);
        if (i >= 3) {
            temp.push_back(0);
        }
    }

    do { // 모든 칸에서 3개를 뽑는 모든 경우의 수
        vector<int> B;
        for (int i = 0; i < N * M; i++) {
            if (temp[i] == 1) {
                B.push_back(s[i]);
            }
        }
        Batch.push_back(B);
    } while (prev_permutation(temp.begin(), temp.end()));
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    input();
    batch();
    Test();
    cout << answer;
    return 0;
}

---

🤔 문제 후기

문제를 푸는 아이디어 자체는 금방 생각 났지만, 생각보다 시간이 너무 오래 걸렸다. 조합의 경우 기억이 잘 나지 않아 구글링을 하여 풀었고, Test() 코드에서 배치를 할 때마다 Map과 virus를 리셋 해줘야 했는데, 이 부분을 제대로 하지 못했다. pres_permutation을 활용하여 조합만 구현할 수 있다면, 그렇게 어려운 문제는 아니였다. 단, 문제 자체가 실수할 수 있는 부분이 조금 있었던 것 같다.