문제

Example Input/Output

// IN
7 7 // N, M
2 0 0 0 1 1 0 // 각 칸 정보
0 0 1 0 1 2 0 // 0 = 빈칸
0 1 1 0 1 0 0 // 1 = 벽
0 1 0 0 0 0 0 // 2 = 바이러스
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
// OUT
27 // 최대 안전 구역 수

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

const int MX = 10;
int world[MX][MX];
bool canMove[MX][MX];

int n, m;

int sim()
{
    queue<pair<int, int>> q;

    // Init
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            canMove[i][j] = world[i][j] == 0;

            if (world[i][j] == 2)
            {
                q.push({i, j});
            }
        }
    }

    // BFS
    while (q.empty() == false)
    {
        pair<int, int> cur = q.front();
        q.pop();

        int r = cur.first;
        int c = cur.second;

        if (r - 1 >= 0 && canMove[r - 1][c])
        {
            canMove[r - 1][c] = false;
            q.push({r - 1, c});
        }

        if (r + 1 < n && canMove[r + 1][c])
        {
            canMove[r + 1][c] = false;
            q.push({r + 1, c});
        }

        if (c - 1 >= 0 && canMove[r][c - 1])
        {
            canMove[r][c - 1] = false;
            q.push({r, c - 1});
        }

        if (c + 1 < m && canMove[r][c + 1])
        {
            canMove[r][c + 1] = false;
            q.push({r, c + 1});
        }
    }

    // Result
    int emptyCount = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (canMove[i][j])
            {
                emptyCount++;
            }
        }
    }

    return emptyCount;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> world[i][j];
        }
    }

    int maxCoord = n * m;
    int maxVirus = 0;

    for (int first = 0; first < maxCoord; first++)
    {
        int firstY = first % m;
        int firstX = first / m;

        if (world[firstX][firstY] != 0)
            continue;

        world[firstX][firstY] = 1;

        for (int second = first + 1; second < maxCoord; second++)
        {
            int secondY = second % m;
            int secondX = second / m;

            if (world[secondX][secondY] != 0)
                continue;

            world[secondX][secondY] = 1;

            for (int third = second + 1; third < maxCoord; third++)
            {
                int thirdY = third % m;
                int thirdX = third / m;

                if (world[thirdX][thirdY] != 0)
                    continue;

                world[thirdX][thirdY] = 1;

                maxVirus = max(maxVirus, sim());

                world[thirdX][thirdY] = 0;
            }

            world[secondX][secondY] = 0;
        }

        world[firstX][firstY] = 0;
    }

    cout << maxVirus;
}

메모

문제 정리

• 3 <= N, M <= 8

• 2 <= 바이러스 수 <= 10

• 3 <= 빈칸 수

• N*M 월드

  • 0: 빈 칸
  • 1: 벽
    • 벽 3개를 새로 세운다
  • 2: 바이러스
    • 바이러스는 상하좌우 퍼져나간다

바이러스가 없는 곳 안전 영역

풀이

• 3중 for문
  1. 3개의 벽을 세우고
  2. 바이러스 BFS
  3. 최대 안전 영역 = max(최대 안전 영역, 현재 안전 영역)

메모

• Column Row 신경쓸 것
• 1151 -> 1156