[백준] 14502번 연구실 (C#)

문제

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

고민

고민이 코드보다 먼저 나오는게 좋을 거 같아서 수정했습니다. 어떠신가요^.^

 

문제를 보면

1. 연구실에 벽 3개를 임의로 설치하고

2. 바이러스를 감염시킨다.

3. 감염되지 않은 공간을 센다.

위 세 로직을 반복하여 감염되지 않은 공간이 가장 많을 경우를 출력하면 된다.

 

우선 1. 연구실에 벽 3개를 임의로 설치

이 문장을 보고 nCr(조합)을 떠올렸다. 조합은 백트래킹으로 찾아줬다.

만약, 3개의 자리에 a, b, c, d, e를 넣는 경우의 수를 생각해보면

a b c

a b d

a b e

a c d

a c e

a d e

...

가 나올 것이다. 나는 이것을 백트래킹이라고 이해했다.

재귀로 계속 호출해주면서 하나씩 값을 넣으면 모든 경우의 수가 나온다.

 

2. 바이러스를 감염시킨다.

바이러스는 상하좌우 1칸씩만 움직인다. 미로찾기 문제와 흡사하다. 이건 BFS로 길을 찾아 빈 공간을 감염시켰다.

 

3. 감염되지 않은 공간을 센다.

이건 그냥 세면 된다.

코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodingTest.Greedy
{
    internal class 연구소
    {
        static int n, m;
        static int[,] lab; // 인접행렬
        static List<(int, int)> empty = new List<(int, int)> (); // 빈 칸 좌표를 담는 리스트
        static List<(int, int)> virus = new List<(int, int)> (); // 바이러스 좌표를 담는 리스트

        static int[] dirX = { -1, 0, 1, 0 };
        static int[] dirY = { 0, -1, 0, 1 }; 

        static int wallCount = 0;
        static int safeAreaCount = 0;

        // 백트래킹
        // 벽을 세우고 벽이 3개가 되면 안전 지대를 계산
        static void BuildWalls(int start)
        {
            if(wallCount >= 3)
            {
                // 바이러스를 이동시켜서
                // 안전 지대 찾기
                int cnt = FindSafeArea();
                if(cnt > safeAreaCount)
                {
                    safeAreaCount = cnt;
                }
                return;
            }

            // 빈 칸을 검색해서
            // 벽을 세운다.
            for (int i = start; i < empty.Count; i++) 
            {
                var (x, y) = empty[i]; // 빈 칸 좌표
                lab[x, y] = 1; // 벽 세우기
                wallCount++;
                BuildWalls(i + 1);

                // 재귀가 끝나면 다시 벽 없애기
                lab[x, y] = 0;
                wallCount--;
            }

        }

        // 바이러스를 이동시켜
        // 안전 지대를 찾는 메서드
        static int FindSafeArea()
        {
            int[,] tempLab = new int[n, m];
            Array.Copy(lab, tempLab, lab.Length);
            Queue<(int, int)> q = new Queue<(int, int)> (); // 바이러스 좌표를 담을 큐

            foreach(var v in virus)
            {
                q.Enqueue(v); // queue에 바이러스 좌표
            }

            while(q.Count > 0)
            {
                var (x, y) = q.Dequeue();
                for (int i = 0; i < 4; i++)
                {
                    int nx = x + dirX[i];
                    int ny = y + dirY[i];
                    if(nx >= 0 && ny >= 0 && nx < n && ny < m && tempLab[nx, ny] == 0)
                    {
                        tempLab[nx, ny] = 2; // 감염
                        q.Enqueue((nx, ny)); // 큐에 등록
                    }
                }
            }

            // 감염 끝난 후 lab을 돌며
            // 오염되지 않은 공간 찾기
            int cnt = 0;
            for (int i = 0; i < n ; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (tempLab[i, j] == 0)
                    {
                        cnt++;
                    }
                }
            }
            return cnt;
        }

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            n = int.Parse(input[0]); // 7
            m = int.Parse(input[1]); // 7

            lab = new int[n, m];

            for(int i = 0; i < n; i++)
            {
                input = Console.ReadLine().Split(' '); // [2, 0, 0, 0, 1, 1, 0]
                for (int j = 0; j < m; j++)
                {
                    lab[i,j] = int.Parse(input[j]); // 2

                    // 빈 칸, 바이러스 좌표를 각각 저장
                    if (lab[i,j] == 0)
                    {
                        empty.Add((i,j));
                    }
                    else if (lab[i,j] == 2)
                    {
                        virus.Add((i,j));
                    }
                }
            }

            BuildWalls(0);
            Console.WriteLine(safeAreaCount);

        }
    }
}