[C#] 코드포스 1829E번 문제풀이

문제번호: 1829E

문제명: E. The Lakes

문제링크: https://codeforces.com/problemset/problem/1829/E

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

오늘은 BFS를 활용하는 문제를 풀었습니다. NxM 크기의 사각형이 주어질 때, 사각형 내부에서 가장 넓은 부피의 호수 크기를 구하는 문제입니다. 방문하지 않은 지점을  찾아내면 BFS를 활용하여 호수의 넓이를 구하고 최대 부피를 갱신하고 출력해주었습니다. 또한 BFS 탐색 중 각 사분면에 대해서 이동할 수 있도록 정적 dx, dy int형 배열을 선언하여 각각 { 1, -1, 0, 0 }, { 0, 0, 1, -1 }을 넣어주었습니다. 위 dx, dy를 활용해 int nx = x + dx[i]; int ny = y + dy[i]; 와 같이 다음 이동할 정점을 구하였습니다.

다음은 정답코드입니다.

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

static void Main()
{
    int t = int.Parse(Console.ReadLine());
    for (int i = 0; i < t; i++)
    {
        int[] nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int n = nm[0];
        int m = nm[1];

        int[,] grid = new int[n, m];
        bool[,] visited = new bool[n, m];

        for (int j = 0; j < n; j++)
        {
            var row = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            for (int k = 0; k < m; k++)
                grid[j, k] = row[k];
        }

        int maxVolume = 0;

        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < m; k++)
            {
                if (grid[j, k] > 0 && !visited[j, k])
                {
                    int volume = BFS(j, k, grid, visited, n, m);
                    maxVolume = Math.Max(maxVolume, volume);
                }
            }
        }

        Console.WriteLine(maxVolume);

    }
}

static int BFS(int sx, int sy, int[,] grid, bool[,] visited, int n, int m)
{
    Queue<(int, int)> queue = new Queue<(int, int)> ();
    queue.Enqueue((sx, sy));
    visited[sx, sy] = true;

    int sum = 0;

    while(queue.Count > 0)
    {
        var (x, y) = queue.Dequeue ();
        sum += grid[x, y];
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];


            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;

            if (grid[nx, ny] == 0 || visited[nx, ny])
                continue;

            visited[nx, ny] = true;
            queue.Enqueue((nx, ny));
        }
    }

    return sum;
}