[알고리즘] 연구소

구현 방식

• 이게 보면,, N, M이 8 이하이고, 시간제한이 2초이다.
• 뭔가 완전 탐색으로 해도 될것같다. 계산해보도록 하자.
• 완전 탐색으로 3개의 벽을 쌓는 경우는 (N x M) ^3 의 경우의 수가 나오고,
• BFS 는 O(V^2) ( V는 정점의 개수)
• N = 8, M = 8 일때 최대 연산량은 (8 x 8 ) ^3 x (8 x 8) ^ 2 이므로, 2^30 이다.
• 최대 연산량이 약 1초 조금 더 걸리므로 2초( 2억번) 연산까지는 가능하다.

코드

• 최종 코드는 아래와 같다.

void solution(int N, int M, int wallCount, vector<pair<int,int>>& virusPos)
{
    // 감염된 지역의 최소값
    int minArea = INT_MAX;
    for (int y1 = 0; y1 < N; y1++)
    {
        for (int x1 = 0; x1 < M; x1++)
        {
            if (graph[y1][x1] != '0') continue;
            for (int y2 = 0; y2 < N; y2++)
            {
                for (int x2 = 0; x2 < M; x2++)
                {
                    if (graph[y2][x2] != '0') continue;
                    if (y1 == y2 && x1 == x2) continue;

                    for (int y3 = 0; y3 < N; y3++)
                    {
                        for (int x3 = 0; x3 < M; x3++)
                        {
                            if (graph[y3][x3] != '0') continue;
                            if (y1 == y3 && x1 == x3) continue;
                            if (y2 == y3 && x2 == x3) continue;

                            graph[y1][x1] = graph[y2][x2] = graph[y3][x3] = '1';
                            int area = 0;
                            for (pair<int, int>& virus : virusPos)
                            {
                                if (!visited[virus.first][virus.second])
                                    area += bfs(N, M, virus);
                            }
                            minArea = min(area, minArea);
                            graph[y1][x1] = graph[y2][x2] = graph[y3][x3] = '0';
                            fill(&visited[0][0], &visited[N - 1][M], false);

                        }
                    }

                }
            }

        }
    }

    cout << N * M - wallCount - minArea - 3;
}


int bfs(const int N, const int M, pair<int,int> start)
{
    int result = 0;
    queue<pair<int,int>> q;
    q.push(start);
    visited[start.first][start.second] = true;
    result++;

    while (!q.empty())
    {
        pair<int, int> curr = q.front();
        q.pop();

        for (auto& dir : Directions)
        {
            pair<int, int> next = {curr.first + dir.first , curr.second + dir.second};
            if (!canGo(N, M, next)) continue;
            q.push(next);
            visited[next.first][next.second] = true;
            result++;
        }
        
    }

    return result;
}

bool canGo(int N, int M, pair<int, int> pos)
{
    if (pos.first < 0 || N <= pos.first)
        return false;
    if (pos.second < 0 || M <= pos.second)
        return false;
    if (graph[pos.first][pos.second] == '1')
        return false;
    return !visited[pos.first][pos.second];
}