Baaaaaaaaaduk2 (Easy) 16988

문제

생략

접근 방법

나눠서 보면 된다.

1. 2개의 바둑돌을 고른다.
2. 상대의 돌이 막혀있는지 확인한다.
3. 막힌 경우 몇 개인지 확인하여 합산한다.

2개의 바둑돌은 어디에 놓아야 최대 개수를 보장하는지 확인할 수 없다. 그렇기에 모든 경우를 확인해 보아야 한다.

상대의 돌의 개수는 그래프 탐색을 통해 확인할 수 있다. 확인하는 과정에서 막혀있지 않다는 것을 알게 된다면 그 경우 값을 반영하지 말아야 한다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
int N, M, ret = 0;
vector<vector<int>> map;
vector<vector<bool>> visted;
vector<pii> pos;
pii choose[2], d[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool isEmpty(int y, int x)
{
    for (int i = 0; i < 4; ++i)
    {
        int ny = y + d[i].first, nx = x + d[i].second;
        if (ny < 0 || nx < 0 || ny >= N || nx >= M)
            continue;
        if (!map[ny][nx])
            return true;
    }
    return false;
}
int bfs(int y, int x)
{
    queue<pair<int, int>> q;
    q.push({y, x});
    int cnt = 1;
    bool isCan = true;
    while (!q.empty())
    {
        pii cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int ny = d[i].first + cur.first, nx = d[i].second + cur.second;
            if (ny < 0 || nx < 0 || ny >= N || nx >= M)
                continue;
            if (!map[ny][nx]) // 뚫려있다는 뜻이다.
                isCan = false;
            if (visted[ny][nx] || map[ny][nx] != 2)
                continue;
            visted[ny][nx] = true;
            ++cnt;
            q.push({ny, nx});
        }
    }
    if (!isCan)
        cnt = 0;
    return cnt;
}
void dfs(int idx, int depth)
{
    if (depth == 2)
    {
        visted = vector<vector<bool>>(N, vector<bool>(M));
        int cnt = 0;
        for (int i = 0; i < 2; ++i)
        {
            for (int j = 0; j < 4; ++j)
            {
                int ny = choose[i].first + d[j].first, nx = choose[i].second + d[j].second;
                if (ny < 0 || nx < 0 || ny >= N || nx >= M || map[ny][nx] != 2 || visted[ny][nx] || isEmpty(ny, nx))
                    continue;
                visted[ny][nx] = true;
                cnt += bfs(ny, nx);
            }
        }
        ret = cnt > ret ? cnt : ret;
        return;
    }
    for (int i = idx; i < pos.size(); ++i)
    {
        choose[depth] = pos[i];
        int y = pos[i].first, x = pos[i].second;
        map[y][x] = 1;
        dfs(i + 1, depth + 1);
        map[y][x] = 0;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    map = vector<vector<int>>(N, vector<int>(M));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
        {
            cin >> map[i][j];
            if (!map[i][j])
                pos.push_back({i, j});
        }
    dfs(0, 0);
    cout << ret;
    return 0;
}

풀이

완전 탐색으로 2개의 위치를 구하고 그래프 탐색으로 영역이 뚫린 영역인지 확인하면 된다.
조심해야 할 점이 있다. 만약 뚫려있는 것을 확인해도 그 상태에서 BFS를 그만두면 안 된다는 점이다.
만약 그 상태에서 BFS를 그만둔다면 방문 확인을 해준 배열이 벽이 되기에 뚫린 영역도 막힌 영역처럼 처리된다.

그러한 점을 유의하지 못하면 틀리게 된다.