백준 15812번 침략자 진아 [C++]

 

 

 

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

#문제 간단 정리

bfs 나 혹은 브루트 포스로 풀 수 있는 문

 

 

#문제 해결 방법

 

우선 감염원 두개를 고르는 로직이 필요하고

 

그리고 감염원에서 각 마을까지의 최대 거리를 찾아주는 bfs를 사용해도 되고

 

한칸씩 전염되는 시뮬레이션을 만들어도 된다

 

나는 후자로 했다

 

이렇게 시뮬레이션 할때 중요한건

 

맵을 복사해서 상태를 감염 진행을 만드는게 중요하다 아래 코드에선 tempBoard라고 보면 될거다

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

vector<vector<int>> board;
vector<vector<int>> tempBoard;
int n, m;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

void contagion() {
    vector<vector<int>> nextBoard = tempBoard;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            if (tempBoard[i][j] == 3) {

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

                    if (0 <= ny && ny < n && 0 <= nx && nx < m) {
                        if (nextBoard[ny][nx] != 3) {
                            nextBoard[ny][nx] = 3;
                        }
                    }

                }

            }

        }
    }
    tempBoard = nextBoard;
}

bool isAllContagion() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 1 && tempBoard[i][j] != 3) {
                return false;
            }
        }
    }

    return true;
}

int main() {

    cin >> n >> m;

    board.resize(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < s.length(); j++) {
            board[i][j] = s[j] - '0';
        }
    }

    vector<pair<int, int>> emptyCells;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 0) {
                emptyCells.push_back({ i, j });
            }
        }
    }

    int minSec = INT_MAX;

    for (size_t i = 0; i < emptyCells.size(); ++i) {
        for (size_t j = i + 1; j < emptyCells.size(); ++j) {
            pair<int, int> a = emptyCells[i];
            pair<int, int> b = emptyCells[j];

            // 복사후 감염원 설정
            tempBoard = board;
            tempBoard[a.first][a.second] = 3;
            tempBoard[b.first][b.second] = 3;

            int sec = 0;
            while (!isAllContagion()) {
                contagion();
                sec++;
            }
            minSec = min(sec, minSec);
        }
    }

    cout << minSec << '\n';

    return 0;
}