[알고리즘 문제 풀기] 연구소(14502)

1. 문제 풀이 아이디어

• 벽 3개를 세우는 모든 조합을 탐색하고, 각각에 대해 바이러스가 퍼졌을 때 감염되지 않은 영역의 최대 크기를 BFS로 계산해 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int n = input[0];
    int m = input[1];
    int[] map = new int[n * m];
    List<int> virus = new List<int>();
    int wall = 3;
    for (int i = 0; i < n; i++)
    {
        input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        for (int j = 0; j < m; j++)
        {
            map[i * m + j] = input[j];
            if (input[j] == 1) wall++;
            else if (input[j] == 2) virus.Add(i * m + j);
        }
    }

    int min = int.MaxValue;
    for (int i = 0; i < n * m - 2; i++)
    {
        if (map[i] != 0) continue;
        map[i] = 1;
        for (int j = i + 1; j < n * m - 1; j++)
        {
            if (map[j] != 0) continue;
            map[j] = 1;
            for (int k = j + 1; k < n * m; k++)
            {
                if (map[k] != 0) continue;
                map[k] = 1;
                min = Math.Min(min, VirusCount());
                map[k] = 0;
            }
            map[j] = 0;
        }
        map[i] = 0;
    }
    sw.WriteLine(n * m - min - wall);

    int VirusCount()
    {
        int result = 0;
        int[] dir = { 1, -1, m, -m };
        bool[] visited = new bool[n * m];
        Queue<int> queue = new Queue<int>(virus);
        while (queue.Count > 0)
        {
            int cur = queue.Dequeue();
            if (visited[cur]) continue;
            visited[cur] = true;
            result++;
            foreach (int nd in dir)
            {
                int nx = cur / m + nd / m;
                int ny = cur % m + nd % m;
                int next = nx * m + ny;
                if (nx < 0 || n <= nx || ny < 0 || m <= ny || map[next] == 1 || visited[next]) continue;
                queue.Enqueue(next);
            }
        }
        return result;
    }
}

3. 정리

• map은 1차원 배열로 사용하며 좌표 변환은 i * m + j를 통해 처리한다.

• 입력 시 벽의 개수를 미리 세고, 바이러스의 위치를 리스트로 저장한다.

• 벽을 세울 수 있는 모든 조합(0인 위치 3곳)을 브루트포스로 탐색한다.

• 각각의 조합마다 VirusCount() 함수로 바이러스의 전파 영역을 BFS로 계산한다.

• 전파된 바이러스 수를 최소로 줄이는 조합을 찾고, 전체 칸에서 벽과 바이러스 영역을 제외하여 안전 영역 최대 크기를 구한다.

• VirusCount() 함수에서 방향 탐색을 위해 dir = {1, -1, m, -m}을 사용하고, 인접 칸이 유효한지 조건을 통해 판단한다.

• 최종적으로 안전 구역의 최대 크기는 전체 칸 수 - 벽 수 - 바이러스 전파 칸 수로 계산한다.