[백준] 1926번 그림(C#)

문제

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

1926번: 그림

코드

namespace dongsik
{
    class Algorithm
    {
        static int n, m;
        static int[,] graph;
        static bool[,] visited;
        static int[] dx = { 1, -1, 0, 0 };
        static int[] dy = { 0, 0, -1, 1 };
        static void Main(string[] args)
        {
            // n * m 입력 받기
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            n = input[0];
            m = input[1];

            // graph 그리기
            graph = new int[n, m];
            visited = new bool[n, m];

            for (int i = 0; i < n; i++)
            {
                int[] inputGraph = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                for (int j = 0; j < m; j++)
                {
                    graph[i, j] = inputGraph[j];
                }
            }

            int picCnt = 0;
            int maxSize = 0;

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (graph[i, j] == 1 && !visited[i, j])
                    {
                        picCnt++;
                        int size = BFS(i, j);
                        maxSize = Math.Max(maxSize, size);
                    }
                }
            }

            Console.WriteLine(picCnt);
            Console.WriteLine(maxSize);
        }

        static int BFS(int x, int y)
        {
            Queue<(int, int)> queue = new Queue<(int, int)>();
            queue.Enqueue((x, y));
            visited[x, y] = true;
            int size = 1;

            while (queue.Count > 0)
            {
                (int cx, int cy) = queue.Dequeue();

                for (int i = 0; i < 4; i++)
                {
                    int nx = cx + dx[i];
                    int ny = cy + dy[i];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && graph[nx, ny] == 1 && !visited[nx, ny])
                    {
                        queue.Enqueue((nx, ny));
                        visited[nx, ny] = true;
                        size++;
                    }
                }
            }
            return size;
        }
    }
}

고민

BFS는 인접한 값을 찾는 것이므로 얼음틀이나 그림처럼 연속되어 연결된 통로를 찾는데 적합하다.

 

BFS로 문제를 풀려면

GRAPH, VISITED

QUEUE가 필요하다.

 

1. 먼저 GRAPH, VISITED를 만들어준다.

2. 만들어진 GRAPH를 돌면서 BFS를 실행시켜준다.

3. BFS는 QUEUE를 사용해서 상하좌우로 이동해주고 이동하면서 조건이 맞는 좌표를 찾는다.

4. 찾으면 해당 좌표를 ENQUEUE한다. 찾지 못하면 반복문이 끝난다.