C# 백준 1012 유기농 배추 (너비우선탐색, 깊이우선탐색)

1012번: 유기농 배추

IDEA

두 알고리즘은 이름에서 나타내는 것처럼 탐색의 우선순위가 다르다. 최초 탐색 지점에서 연결된 곳들을 순차적으로 확인하는 너비우선탐색(BFS)은 한 계층의 정점을 모두 확인하고 다음 계층으로 내려가기 때문에 최단거리를 찾는 탐색에서 유리하다. 깊이우선탐색(DFS)은 탐색 경로를 기억해둬야할 때 유리하다. 모든 정점을 탐색해야하는 문제에서는 어떤 알고리즘을 선택해도 시간복잡도 상의 차이는 없다. 이 문제는 모든 정점을 탐색해야하는 문제이기 때문에 너비우선탐색, 깊이우선탐색 알고리즘을 모두 적용할 수 있다. 

 

너비우선 탐색(Breath First Search)

큐를 통해 구현한다. 2차원 배열을 선언하고 모든 칸을 탐색하면서 배추를 찾을 때마다 너비우선탐색을 실시하고 탐색 횟수를 출력해주면 된다. 너비우선탐색은 큐를 이용해 간단하게 구현할 수 있다. 배열을 확인하다 배추를 발견했을 때, 배추의 위치를 큐에 입력해준다. 그리고 배열 확인을 잠시 멈추고 큐에 입력된 좌표의 상하좌우를 확인해 인접한 배추의 위치를 다시 큐에 입력하고 지금 기준이 된 배추를 큐에서 삭제한다. 큐는 선입선출(FIFO)의 자료구조이기 때문에 매 탐색마다 순차적으로 입력된 좌표를 확인한다. 한 수준을 탐색을 모두 끝내고 다음 수준으로 넘어가서 탐색을 실행하는 방식이다.

 

이런 형태의 그래프가 주어졌다고 해보자. 모든 정점은 상하좌우의 맞닿은 정점과 양방향 간선으로 연결되어있고 대각선은 연결되어있지 않다. 이런 그래프에서 너비우선탐색을 실시한다면 좌상단부터 우하단까지 우선 정점을 찾는다. 가장 먼저 발견한 정점을 큐에 입력한다. 큐에 입력된 정점들을 순차적으로 탐색한다. 정점의 우측 좌표부터 시계방향으로 우측, 하단, 좌측, 상단을 탐색한다. 새로 발견한 정점은 큐에 다시 입력한다. 한차례 탐색이 끝나면 현 위치를 큐에서 제거하고 이 곳은 탐색을 마쳤다는 표시를 남겨둔다.

 

정점 1에서는 2, 3을 찾을 수 있다. 2에서는 4, 3에서는 5를 찾는다. 여기서 더 이상 새로 발견되는 정점이 없게된다.

 

모든 정점을 탐색하고 큐가 비어있으면 탐색 횟수를 1 증가시킨다. 이게 하나의 구역으로 연결된 것이다. 다시 배열을 탐색해 새로운 정점을 찾는다. 새롭게 찾은 정점에서 같은 과정을 반복하고 모든 정점을 탐색한다.

 

깊이우선탐색(Depth First Search)

스택 또는 재귀를 통해 구현한다. 하나의 정점에서 간선으로 연결된 다른 정점을 발견하면 바로 그 정점으로 탐색 범위를 옮긴다. 그 정점도 연결된 다른 정점이 있다면 계속해서 탐색 범위를 옮긴다. 더 이상 연결된 정점이 없다면 상위 정점으로 돌아와 다른 정점을 탐색한다. 모든 정점을 탐색하고 최초 정점으로 돌아올 때까지 탐색을 수행한다.

 

너비우선탐색에서는 한 정점에서 맞닿은 정점을 모두 탐색하고 넘어갔지만 여기서는 1에서 2, 2에서 3, 3에서 4, 4에서 5 순서로 넘어간 곳마다 이어진 정점을 계속해서 탐색한다.

 

마지막 탐색에서 1에서 2, 2에서 3을 탐색했다. 3번 정점에서 더 이상 연결된 정점이 없으니 상위 정점인 2번으로 돌아간다. 2번에 아직 연결된 정점이 남아있기 때문에 다시 연결된 정점으로 넘어가 4, 5 정점을 이어서 탐색하고 실행이 끝난다.

 

CODE 1 너비우선탐색

using System;
using System.Collections.Generic;
public class Location	// 큐에 좌표를 입력하기 위한 2차원 자료구조
{
    public int x;
    public int y;
    public Location(int a, int b)
    {
        x = a; y = b;
    }
}
class Program
{
    static int T, M, N, K, x, y, worm;
    static int[,] field = new int[50, 50];
    static bool[,] check = new bool[50, 50];
    static Queue<Location> BFS = new Queue<Location>();
    static void Main()
    {
        T = int.Parse(Console.ReadLine());
        for (int i = 0; i < T; i++)
        {
            var mnk = Console.ReadLine().Split();
            M = int.Parse(mnk[0]); N = int.Parse(mnk[1]); K = int.Parse(mnk[2]);
            worm = 0;
            for(int j = 0; j < N; j++)
            {
                for(int k = 0; k < M; k++)
                {
                    field[j, k] = 0; check[j, k] = false;
                }
            }
            for(int j = 0; j < K; j++)
            {
                var xy = Console.ReadLine().Split();
                x = int.Parse(xy[1]); y = int.Parse(xy[0]);
                // x가 세로로 가는게 편해서 순서를 바꿨다.
                field[x, y] = 1;
            }
            for(int j = 0; j < N; j++)
            {
                for(int k = 0; k < M; k++)
                {
                    if(field[j,k] == 1 && !check[j, k])	// 배열을 탐색한다.
                    {
                        BFS.Enqueue(new Location(j, k));
                        // 배추가 있고 탐색하지 않은 곳이라면 큐에 입력한다.
                        check[j, k] = true;
                        while(BFS.Count > 0)	// 큐가 비어있을 때까지 반복
                        {
                            x = BFS.Peek().x; y = BFS.Peek().y;
                            
                            if (x > 0 && field[x - 1, y] == 1 && !check[x - 1, y])
                            { BFS.Enqueue(new Location(x - 1, y)); check[x - 1, y] = true; }
                            
                            if (y > 0 && field[x, y - 1] == 1 && !check[x, y - 1])
                            { BFS.Enqueue(new Location(x, y - 1)); check[x, y - 1] = true; }
                            
                            if (x < N - 1 && field[x + 1, y] == 1 && !check[x + 1, y])
                            { BFS.Enqueue(new Location(x + 1, y)); check[x + 1, y] = true; }
                            
                            if (y < M - 1 && field[x, y + 1] == 1 && !check[x, y + 1])
                            { BFS.Enqueue(new Location(x, y + 1)); check[x, y + 1] = true; }
                            
                            BFS.Dequeue();
                            // 상하좌우를 확인했으면 큐에서 제거한다.
                        }
                        worm++;
                        // 한 차례 탐색이 끝났다.
                        // 지렁이가 움직일 수 있는 곳만 탐색했기 때문에
                        // 지렁이 한 마리 추가
                    }
                }
            }
            Console.WriteLine(worm);
        }
    }
}

 

CODE 2 깊이우선탐색

using System;

class Program
{
    static int T, M, N, K, X, Y, worm;
    static int[,] field = new int[50, 50];
    static void Main()
    {
        T = int.Parse(Console.ReadLine());
        for (int i = 0; i < T; i++)
        {
            worm = 0;
            for(int i = 0; i < 50; i++)
            {
            	for(int j = 0; j < 50; j++)
                	field[i, j] = 0;
            }
            var MNK = Console.ReadLine().Split();
            M = int.Parse(MNK[0]);
            N = int.Parse(MNK[1]);
            K = int.Parse(MNK[2]);
            for(int i = 0; i < K; i++)
            {
            	var XY = Console.ReadLine().Split();
            	X = int.Parse(XY[1]);
            	Y = int.Parse(XY[0]);
            	field[X, Y] = 1;
            }
            for(int j = 0; j < N; j++)
            {
                for(int k = 0; k < M; k++)
                {
                    if (field[j, k] == 1)
                    {
                        worm++;	// DFS에 한 번 진입할 때마다 지렁이 1마리 증가
                        DFS(j, k);
                    }
                }
            }
            Console.WriteLine(worm);
        }
    }

    static void DFS(int x, int y)
    {
        field[x, y] = 2;
        
        if(x < N - 1 && field[x + 1, y] == 1)
            DFS(x + 1, y);	// 재귀호출
                
        if (y < M - 1 && field[x, y + 1] == 1)
            DFS(x, y + 1);
            
        if (x > 0 && field[x - 1, y] == 1)
            DFS(x - 1, y);
            
        if (y > 0 && field[x, y - 1] == 1)
            DFS(x, y - 1);
            
        else return;		// 인접한 정점을 모두 탐색했다면 상위 정점으로 돌아간다.
    }
}