[Algorithm]Baekjoon 14502번 :: 연구소

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

14502번: 연구소

struct Node
{
    int y;
    int x;
};
 
int row, column;
int arr[8][8];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
int initZeroCount = 0;
vector<Node> viruses;
vector<Node> walls;
int maxZeroCount = 0;
int maxIndex = 0;
 
int BFS()
{
    int tempMap[8][8];
    int tempZeroCount = initZeroCount;
 
    memcpy(tempMap, arr, 4 * 8 * 8);
    
    for (int i = 0; i < walls.size(); i++)
    {
        tempMap[walls[i].y][walls[i].x] = 1;
    }
 
    for (int i = 0; i < viruses.size(); i++)
    {
        queue<Node> q;
        q.push({ viruses[i].y,viruses[i].x });
 
        while (!q.empty())
        {
            Node popedNode = q.front();
            q.pop();
 
            int curY = popedNode.y;
            int curX = popedNode.x;
 
            for (int i = 0; i < 4; i++)
            {
                int nextY = curY + dir[i][0];
                int nextX = curX + dir[i][1];
 
                if (nextY < 0 || nextY >= row) continue;
                if (nextX < 0 || nextX >= column) continue;
 
                if (tempMap[nextY][nextX] == 0) // 0인곳에서만 전파가능.
                {
                    tempMap[nextY][nextX] = 2;
                    q.push({ nextY,nextX });
                    tempZeroCount--;
                }
            }
        }
    }
 
    return tempZeroCount - 3;
}
 
void DFS(int index)
{
    if (walls.size() == 3)
    {
        maxZeroCount = max(maxZeroCount, BFS());
        return;
    }
 
    for (int i = index; i < maxIndex; i++)
    {
        int ny = i / column;
        int nx = i % column;
 
        if (arr[ny][nx] == 0)
        {
            walls.push_back({ ny,nx });
 
            DFS(i);
 
            if (!walls.empty())
            {
                walls.pop_back();
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> row >> column;
 
    maxIndex = row * column;
 
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 0)
            {
                initZeroCount++;
            }
 
            if (arr[i][j] == 2)
            {
                viruses.push_back({ i,j });
            }
        }
    }
 
    DFS(0);
 
    cout << maxZeroCount;
}
 

DFS와 BFS, 조합개념이 들어가는 문제이다.

벽 3개를 세웠을 때, 0의 개수가 가장 많은 경우의 0의 개수를 리턴하면 된다.

그렇다면 먼저 벽 3개를 모든 경우의 수에 대하여 설치해봐야 한다.

여기서 벽 3개의 인덱스를 뽑을 때 '조합'으로 뽑는다. 즉, 순서없는 집합이다.

1,2,3을 뽑든, 3,2,1을 뽑든 같은 경우의 수이다.

그렇기 때문에 위 DFS코드에서 반복문을 돌릴때 들어온 index를 시작으로 잡고 돌리는 것이다.

 

코드를 보면 알겠지만 2차원 맵에대한 인덱스를 1차원으로 표현해서 코드를 작성했다.

0,0 -> 0. 

0,1 -> 1

0,2 -> 2... 이런식으로 바꿔서 표현했다.

 

반드시 이렇게 할 필요는 없지만, 재귀를 돌릴때 2차원배열을 한칸씩 탐색하는걸 쉽게 표현하기위해 바꿔봤다.

그리고 나는 선택한 배열의 칸을 스택에 담아서 관리했다.

최대 설치개수인 3개가 될때마다 최대 0의 개수를 업데이트하고, 다시 pop한다음 그다음껄 선택해서 집어넣는 형식이다.

 

BFS돌릴 때는 당연히 기존맵을 복사해서 사용해야한다. 그냥 그대로 복사하면 되서 memcpy로 복사했다.

벽을 설치 후, 각 바이러스를 기준으로 퍼뜨렸다. 

빈 공간에 바이러스를 퍼뜨릴때마다 기존의 0의개수에서 한개씩 차감하는 방식으로 했다.

마지막에 -3을 하는 이유는 기존의 맵에서 벽을 3개를 추가로 설치했기 때문이다. 0인공간에 설치하는 것이기 때문에 3을 차감해줘야 한다.