[백준 14502] 연구소

생각보다 얘를 먹으면서 풀었다.

 

벽 3개를 놓을때 DFS로 조합론 구현해서 중복없이 세운 뒤

벽 3개를 만족했을 시, check 함수를 통해 안전영역의 최대 크기를 계산하고 업데이트하게 하였다.

 

---

[ 특정 좌표(row, col)를 정수값으로 표현 ]

 

벽을 3개 세우는 과정에서 map의 어느 부분부터 시작해서 채울지를 표현해야했다.

이때 그냥 특정 좌표 (row, col)을 정수값을 표현하여 계산했다.

    // N = 3 M = 4
    // 0 1 2 3
    // 4 5 6 7
    // 8 9 10 11
    for (int i = start; i < N * M; i++)
    {
        int row = i / M;
        int col = i % M;

        if (temp[row][col] == 0)
        {
            temp[row][col] = 1;
            create_wall(temp, i + 1, cnt + 1);
            temp[row][col] = 0;
        }
    }

 

[ 2차원 배열의 깊은 복사 ]

 

중요한 것은 2차원 배열 즉, map에 대한 관리였다.

그냥 인자로 넘겨버리면 얕은 복사, 즉 포인터가 인자로 전달되어 기존 map 배열을 오염시킬 수 있다.

따라서 memcpy를 사용한 깊은 복사를 통해 더미 배열 하나를 더 만들어서 인자로 넘겨주어야한다.

#include <cstring>

memcpy(temp, map, sizeof(map));
memcpy(temp, map, sizeof(int) * SIZE * SIZE));

 

---

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define SIZE 8

using namespace std;

int N, M;
int map[SIZE][SIZE];
int temp[SIZE][SIZE];
vector<pair<int, int>> virus;

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

int ans = 0;

// temp 배열에 대한 포인터가 들어옴
void check(int temp[SIZE][SIZE])
{
    for (int i = 0; i < virus.size(); i++)
    {
        queue<pair<int, int>> q;
        q.push(virus[i]);

        while (!q.empty())
        {
            auto [y, x] = q.front();
            q.pop();

            for (int i = 0; i < 4; i++)
            {
                int nexty = y + dy[i];
                int nextx = x + dx[i];

                if (nexty < 0 || nextx < 0 || nexty >= N || nextx >= M)
                {
                    continue;
                }

                if (temp[nexty][nextx] == 0)
                {
                    temp[nexty][nextx] = 2;
                    q.push(make_pair(nexty, nextx));
                }
            }
        }
    }

    // 0 개수 세기
    int total = 0;
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            if (temp[i][k] == 0)
            {
                total++;
            }
        }
    }

    ans = max(ans, total);
}

// 기존 map에 대한 포인터가 들어옴
void create_wall(int map[SIZE][SIZE], int start, int cnt)
{
    if (cnt == 3)
    {
        memcpy(temp, map, sizeof(int) * SIZE * SIZE);
        check(temp);
        return;
    }

    // N = 3 M = 4
    // 0 1 2 3
    // 4 5 6 7
    // 8 9 10 11
    for (int i = start; i < N * M; i++)
    {
        int row = i / M;
        int col = i % M;

        if (map[row][col] == 0)
        {
            map[row][col] = 1;
            create_wall(map, i + 1, cnt + 1);
            map[row][col] = 0;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            cin >> map[i][k];
            if (map[i][k] == 2)
            {
                virus.push_back(make_pair(i, k));
            }
        }
    }

    create_wall(map, 0, 0);

    cout << ans;

    return 0;
}