[ 백준 17142 ] 연구소 3 (C++) - BFS, 시뮬레이션

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 간단하다. 모든 칸은 감염시켜야 한다.
2. 정해진 갯수를 골라서 모든 칸을 감염시키는데 걸리는 시간이 최소가 되게 해야한다. 단, 감염시킬 수 없는 칸이 존재한다면 -1을 반환한다.
3. 애먹은 점이 이 조건이다. 바이러스를 활성화 시켰을 때, 비활성 바이러스도 있는 것으로 간주한다. 이는 비활성 바이러스가 있는 칸을 감염시키며 나아갈 수는 있지만, 감염시키지 않아도 그 칸은 감염되어 있는 것으로 간주한다는 뜻이다. 이를 설명하는 설명 예시이다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define INF 987654321

using namespace std;

int N, M, need = 0; // need = 감염시켜야할 남은 블록수
struct NODE {
    int status = INF;
    int origin = 0;
};

NODE MAP[50][50];

int next_x[] = {-1, 1, 0, 0};
int next_y[] = {0, 0, 1, -1};
vector<pair<int, int> > starting;
vector<vector<pair<int, int> > > answer;

void input() {
    cin >> N >> M;
    int num;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            cin >> num;
            if (num == 0) {
                MAP[y][x].status = INF;
            } else if (num == 2) {
                MAP[y][x].origin = 2;
                MAP[y][x].status = INF;
                starting.push_back({x, y});
            } else if (num == 1) {
                MAP[y][x].origin = 1;
                MAP[y][x].status = -1;
            }
        }
    }
}

void combination(int depth, int next, vector<pair<int, int> > tempAnswer) {
    if (depth == M) {
        answer.push_back(tempAnswer);
        return;
    }

    for (int i = next; i < starting.size(); i++) {
        tempAnswer.push_back({starting[i].first, starting[i].second});
        combination(depth + 1, i + 1, tempAnswer);
        tempAnswer.pop_back();
    }
}

int bfs(vector<pair<int, int>> test) {

    queue<pair<int, int> > q;
    for (pair<int, int> i: test) {
        q.push({i.first, i.second});
        MAP[i.second][i.first].status = 0;
    }

    while (!q.empty()) {
        int q_size = q.size();
        for (int i = 0; i < q_size; i++) {
            int cx = q.front().first, cy = q.front().second;
            q.pop();

            for (int j = 0; j < 4; j++) {
                int nx = cx + next_x[j], ny = cy + next_y[j];
                if (nx > -1 && ny > -1 && nx < N && ny < N && MAP[ny][nx].status != -1) {
                    if (MAP[ny][nx].status > MAP[cy][cx].status + 1) {
                        q.push({nx, ny});
                        MAP[ny][nx].status = MAP[cy][cx].status + 1;
                    }
                    if (MAP[ny][nx].status == -2) {
                        q.push({nx,ny});
                    }
                }
            }
        }
    }

    int answer = 0;
    for(int y=0; y<N; y++) {
        for(int x=0; x<N; x++) {
            if(MAP[y][x].origin == 2) continue;
            if(MAP[y][x].status == INF) return INF;
            answer=max(answer,MAP[y][x].status);
        }
    }

    return answer;
}

int main() {

    input();
    vector<pair<int, int> > tempAnswer;
    combination(0, 0, tempAnswer);

    int ans = INF;
    for (auto test : answer) {
        for(int y=0; y<N; y++) {
            for(int x=0; x<N; x++) {
                if(MAP[y][x].origin != 1) MAP[y][x].status=INF;
            }
        }
        ans = min(ans,bfs(test));
    }
    if(ans == INF) cout<<-1;
    else cout <<ans;

    return 0;
}

---

🤔 문제 후기

가장 어려운 부분은 개인적으로 조합이였다. 문제는 평범한 BFS고 시간복잡도를 계산해봤을 때, 완전탐색으로 풀 수 있기에 머리를 쓸 일은 조합을 구현하는 것 밖에 없었다. 분명히 next_permutaion인가 그런게 있었는데,,, 기억이 안나서 조합을 어떻게 만들지 생각하고 구현하는 것에만 거의 1시간이 걸렸고, 나머지는 시간이 거의 걸리지 않았다. 제출하고 98%에서 틀렸었는데, 예제를 struct로 이미 감염된 곳이면 넘어가는 방식으로 해결하고 나니 통과되었다. 조합 순열 등은 코테때 외우고 가는게 맞는 것 같다...