C# : 백준 <유기농 배추>

---

해당 문제는 BFS와 DFS 모두를 이용하며 풀 수 있다. 먼저 각 알고리즘의 특징이 무엇인지 알아야한다.

1. BFS(너비 우선 탐색)란?

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

 

using System;
using System.Collections.Generic;

class MainClass
{
    static int[,] field; // 배추밭 배열
    static bool[,] visited; // 방문 여부를 저장하는 배열
    static int[] dx = { -1, 1, 0, 0 }; // 상하좌우 이동을 위한 배열
    static int[] dy = { 0, 0, -1, 1 };
    static int m, n; // 가로길이, 세로길이

    static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine()); // 테스트 케이스 개수 입력 받기

        for (int t = 0; t < T; t++)
        {
            string[] input = Console.ReadLine().Split();
            m = int.Parse(input[0]); // 가로길이 입력 받기
            n = int.Parse(input[1]); // 세로길이 입력 받기
            int k = int.Parse(input[2]); // 배추 개수 입력 받기

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

            for (int i = 0; i < k; i++)
            {
                string[] pos = Console.ReadLine().Split();
                int x = int.Parse(pos[0]); // 배추의 x 좌표
                int y = int.Parse(pos[1]); // 배추의 y 좌표

                field[x, y] = 1; // 배추가 있는 위치 표시
            }

            int wormCount = 0; // 배추흰지렁이의 수

            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (field[i, j] == 1 && !visited[i, j])
                    {
                        BFS(i, j); // BFS 호출
                        wormCount++; // 새로운 배추흰지렁이 그룹을 찾았으므로 개수 증가
                    }
                }
            }

            Console.WriteLine(wormCount); // 결과 출력
        }
    }

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

        while (queue.Count > 0)
        {
            var (curX, curY) = queue.Dequeue();

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

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

 

2. DFS(깊이 우선 탐색)란?

현재 위치에서 출발하여 연결된 모든 정점을 탐색하는 알고리즘으로, 스택 또는 재귀함수를 사용하여

구현가능하다. 이때 재귀함수를 이용한 DFS는 현재 위치에서 인접한 위치를 순차적으로 탐색하며, 각 위치를 방문처리하여 연결된 것을 탐색하고 그룹을 형성한다는 특징이 있다. 

 

using System;

namespace test2
{
    internal class Program
    {
        static int[,] field;                // 배추밭의 정보를 저장할 2차원 배열
        static bool[,] visited;             // 방문 여부를 저장할 2차원 배열
        static int[] dx = { -1, 1, 0, 0 };  // 상하좌우 이동을 위한 배열
        static int[] dy = { 0, 0, -1, 1 };
        static int m, n;                    // 배추밭의 가로, 세로 길이
        static void Main(string[] args)
        {

            int t = int.Parse(Console.ReadLine());      // 테스트 케이스의 개수 T
            for(int i = 0; i < t; i++)                  // T만큼 반복한다
            {
                string[] input =  Console.ReadLine().Split();
                m = int.Parse(input[0]);                // 배추 밭의 가로길이
                n = int.Parse(input[1]);                // 배추 밭의 세로길이
                int k = int.Parse(input[2]);            // 배추의 위치 개수 K

                field = new int[m, n];
                visited = new bool[m, n];
                for(int j = 0; j < k; j++)              // 배추의 위치 개수만큼 입력 받는다
                {
                    string[] pos = Console.ReadLine().Split();
                    int x = int.Parse(pos[0]);
                    int y = int.Parse(pos[1]);
                    field[x, y] = 1;                    // 배추의 위치를 1로 표시한다
                }

                int count = 0;                          // 필요한 배추흰지렁이 수
                for(int x =0; x< m;x++)
                {
                    for(int y =0; y<n; y++) 
                    {
                        // 배추가 심어져있고 방문하지 않은경우
                        if (field[x,y] ==1 && !visited[x,y])
                        {
                            DFS(x, y);
                            count++;
                        }
                            
                    }
                }

                Console.WriteLine(count);
            }

        }

        static void DFS(int x, int y)
        {
            visited[x,y] = true;                        // 현재 위치 방문 처리한다
            for(int i=0;i<4;i++)                        // 상하 좌우 이동을 위한 반복문
            {              
                int nx = x + dx[i];                     // 새로운 x좌표 계산
                int ny = y + dy[i];                     // 새로운 y좌표 계산
                if(nx>=0&&nx<m && ny>=0 && ny<n)        // 유효한 땅인지 검사
                {
                    // 상하좌우 중에 배추가 있다면 인접한 경우이므로
                    if (field[nx,ny] == 1 && !visited[nx,ny])
                    {
                        // 다시 그 배추를 기준으로 인접한 곳을 찾아야한다
                        DFS(nx, ny);
                    }
                }
            }

        }
    }
}

 

3. 결과

결과적으론 DFS가 시간과 메모리적으로 더 효율이 높게 나왔다. BFS도 더 좋은 코드라면 가능할진 모르겠지만 일단 내 결과는 이랬던걸로!