연구소 14502

문제

접근 방법

범위를 좁게 주고 선택하는 경우도 적게 주었다=>모든 경우를 확인해봐라.
라고 볼 수 있는 것 같다.

최대 지도 8*8
64C3(벽 1, 2, 3)*64(세균 확산)*64(안전 영역 확인)=1억 정도이다.

조합을 하여 벽 3곳을 정하고 세균을 BFS 한 뒤 안전 영역인지 확인하는 방식으로 풀면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int map[8][8], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, N, M, ret = 0;
bool visted[8][8];
vector<pair<int, int>> virus, emptySpace;
void bfs()
{
    int cnt = 0;
    memset(visted, false, sizeof(visted));
    queue<pair<int, int>> q;
    for (auto v : virus)
        q.push(v);
    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> next = {cur.first + dy[i], cur.second + dx[i]};
            if (next.first < 0 || next.second < 0 || next.first >= N || next.second >= M)
                continue;
            if (map[next.first][next.second] || visted[next.first][next.second])
                continue;
            visted[next.first][next.second] = true;
            q.push(next);
        }
    }
    for (auto es : emptySpace)
    {
        if (visted[es.first][es.second] || map[es.first][es.second])
            continue;
        ++cnt;
    }
    ret = cnt > ret ? cnt : ret;
}
void dfs(int cnt, int idx)
{
    if (cnt == 3)
    {
        bfs();
        return;
    }
    for (int i = idx; i < emptySpace.size(); ++i)
    {
        pair<int, int> cur = emptySpace[i];
        map[cur.first][cur.second] = 1;
        dfs(cnt + 1, i + 1);
        map[cur.first][cur.second] = 0;
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
        {
            cin >> map[i][j];
            if (!map[i][j])
                emptySpace.push_back({i, j});
            else if (map[i][j] == 2)
                virus.push_back({i, j});
        }
    dfs(0, 0);
    cout << ret;
    return 0;
}

풀이

조합을 쉽게 하려고 0인 곳들을 저장해두었다.
벽 3곳을 정한 뒤 세균을 BFS 해주고 0을 저장해둔 곳을 재활용하면 덜 탐색해도 된다고 생각했다.