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

📌문제 링크

---

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

📌문제 설명

---

빈 공간과 마을 위치를 입력받아, 빈 공간에서 가능한 두 좌표의 조합을 생성하고, BFS(너비 우선 탐색)를 통해 독이 퍼지는 시간을 계산합니다. 모든 마을이 독에 감염되는 최소 시간을 찾기 위해 각 조합에 대해 독의 확산 여부를 초기화하고 탐색하며, 최적의 시간을 갱신합니다. 최종적으로 가장 빠르게 독이 퍼질 수 있는 최소 시간을 출력합니다.

📌코드

---

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

// 좌표를 저장하는 벡터
vector<pair<int, int>> v1; // 빈 공간 좌표를 저장
vector<pair<int, int>> v2; // 마을(1인 곳)의 좌표를 저장

// 지도와 독 퍼짐 여부를 기록하는 배열
bool poison[21][21]; // 특정 칸에 독이 퍼졌는지 여부
char mp[21][21]; // 지도

// 지도 크기와 결과를 저장할 변수
int N, M, mn = INT_MAX;

// 방향 이동 배열 (상하좌우 이동용)
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// BFS에서 사용할 구조체
struct comp {
    int x, y, cnt; // 좌표와 현재 시간(독이 퍼지는 단계)
};

// 지도 입력 처리 함수
void input() {
    cin >> N >> M; // 지도 크기 입력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> mp[i][j]; // 지도 정보 입력
            if (mp[i][j] == '0') {
                v1.push_back({i, j}); // 빈 공간 좌표 저장
            } else if (mp[i][j] == '1') {
                v2.push_back({i, j}); // 마을 좌표 저장
            }
        }
    }
}

// 독 퍼짐 여부 초기화 함수
void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            poison[i][j] = false; // 독 퍼짐 여부를 초기화
        }
    }
}

// BFS를 수행해 특정 독주머니 위치에서 퍼지는 시간을 계산하는 함수
void bfs(int firstx, int firsty, int secondx, int secondy) {
    queue<comp> q; // BFS를 위한 큐

    // 초기 독주머니 위치를 큐에 추가
    q.push({firstx, firsty, 1}); // 첫 번째 독주머니 위치
    q.push({secondx, secondy, 1}); // 두 번째 독주머니 위치

    // 독 퍼짐 여부 표시
    poison[firstx][firsty] = true;
    poison[secondx][secondy] = true;

    // BFS 수행
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt; // 현재 시간(독 퍼지는 단계)
        q.pop();

        // 모든 마을이 독에 감염되었는지 확인
        bool flag = true;
        for (auto it : v2) { // 모든 마을 좌표를 확인
            if (!poison[it.first][it.second]) { // 독에 감염되지 않은 마을이 있다면
                flag = false;
                break;
            }
        }

        // 모든 마을이 감염되었으면 최솟값 갱신 후 종료
        if (flag) {
            mn = min(mn, cnt);
            break;
        }

        // 현재 위치에서 상하좌우로 독 확산
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위를 벗어나거나 이미 감염된 곳은 건너뜀
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (poison[nx][ny]) continue;

            // 독 퍼짐 표시 및 큐에 추가
            poison[nx][ny] = true;
            q.push({nx, ny, cnt + 1});
        }
    }
}

// 독주머니를 설치할 최적의 위치를 찾는 함수
void solve() {
    input(); // 입력 처리

    // 빈 공간에서 두 좌표를 조합으로 선택
    for (int i = 0; i < v1.size(); i++) {
        for (int j = i + 1; j < v1.size(); j++) {
            init(); // 독 퍼짐 여부 초기화
            bfs(v1[i].first, v1[i].second, v1[j].first, v1[j].second); // BFS 수행
        }
    }

    // 결과 출력
    cout << mn;
}

// 메인 함수
int main() {
    ios::sync_with_stdio(0); // 입출력 속도 향상
    cin.tie(0);
    cout.tie(0);

    solve(); // 문제 해결 함수 호출
    return 0;
}