C# 코딩테스트 강좌, 미로 탐색하기

안녕하세요! 이번 강좌에서는 C# 알고리즘 코딩테스트의 한 예제로 미로 탐색 문제를 다루어 보겠습니다. 미로 탐색 문제는 그래프 이론과 DFS(Depth-First Search), BFS(Breadth-First Search) 알고리즘을 이해하는 데 매우 유용합니다. 이 강좌에서는 문제를 정의하고, 입력 형식, 출력 형식, 해결 알고리즘을 단계적으로 설명하겠습니다.

1. 문제 정의

주어진 2차원 배열로 구성된 미로에서 시작점에서 도착점까지 도달할 수 있는 방법의 수를 세는 문제입니다. 미로는 다음과 같은 규칙을 따릅니다:

  • 0은 이동 가능한 경로를 나타냅니다.
  • 1은 이동 불가능한 벽을 나타냅니다.

예를 들어, 다음과 같은 미로가 주어진다면:

0 1 0 0
0 1 0 1
0 0 0 0
1 1 0 1

이 미로에서 (0,0)에서 (3,2)까지 가는 모든 경로의 수를 세는 것이 우리의 목표입니다.

2. 입력 형식

첫 번째 줄에는 미로의 세로 크기 n과 가로 크기 m이 공백으로 구분되어 주어집니다. 두 번째 줄부터 n개의 줄에 걸쳐 미로가 0과 1로 주어집니다.

3. 출력 형식

시작점에서 도착점까지 도달할 수 있는 경로의 수를 출력합니다.

4. 접근 방식

이 문제를 해결하기 위해 BFS를 사용할 것입니다. BFS는 너비 우선 탐색으로, 주어진 그래프에서 최단 경로를 찾거나 특정 조건의 경로를 찾는 데 적합합니다. 문제를 해결하기 위한 단계는 다음과 같습니다:

  1. 미로의 시작점을 큐에 넣고 방문 여부를 배열에 기록합니다.
  2. 큐에서 현재 위치를 꺼내고, 상하좌우로 이동할 수 있는 위치를 확인합니다.
  3. 이동할 수 있는 위치가 방문하지 않은 곳이라면 큐에 추가하고 방문 여부를 기록합니다.
  4. 목적지에 도착하면 경로 수를 증가시킵니다.
  5. 모든 경로가 탐색될 때까지 반복합니다.

5. C# 코드 구현

이제 C#으로 이 알고리즘을 구현해 보겠습니다. 아래는 미로 탐색을 위한 C# 코드입니다.

using System;
using System.Collections.Generic;

class Program
{
    static int n, m;
    static int[,] maze;
    static bool[,] visited;
    static int[] deltaRow = { -1, 1, 0, 0 };
    static int[] deltaCol = { 0, 0, -1, 1 };
    static int pathCount = 0;

    static void Main()
    {
        // 입력 받기
        string[] inputs = Console.ReadLine().Split(' ');
        n = int.Parse(inputs[0]);
        m = int.Parse(inputs[1]);
        maze = new int[n, m];
        visited = new bool[n, m];

        for (int i = 0; i < n; i++)
        {
            string row = Console.ReadLine();
            for (int j = 0; j < m; j++)
            {
                maze[i, j] = row[j] - '0'; // '0'과 '1'을 정수로 변환
            }
        }

        // BFS 탐색 시작
        BFS(0, 0);
        Console.WriteLine("도달 가능한 경로의 수: " + pathCount);
    }

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

        while (queue.Count > 0)
        {
            var (currentRow, currentCol) = queue.Dequeue();

            // 도착점 확인
            if (currentRow == n - 1 && currentCol == m - 1)
            {
                pathCount++;
                continue; // 다른 경로를 계속 탐색
            }

            // 상하좌우 탐색
            for (int i = 0; i < 4; i++)
            {
                int newRow = currentRow + deltaRow[i];
                int newCol = currentCol + deltaCol[i];

                // 범위 체크 및 이동 가능 여부 체크
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && 
                    maze[newRow, newCol] == 0 && !visited[newRow, newCol])
                {
                    visited[newRow, newCol] = true;
                    queue.Enqueue((newRow, newCol));
                }
            }
        }
    }
}

위 코드는 BFS를 이용하여 미로를 탐색하고, 도착점에 도달할 때마다 경로의 수를 증가시키는 기능을 합니다. 이 코드는 시작점 (0, 0)에서 시작하여 도착점 (n-1, m-1)까지 가능한 모든 경로를 탐색합니다.

6. 코드 설명

코드의 주요 부분을 구체적으로 설명하겠습니다.

6.1. 입력 처리

입력 부분에서는 먼저 미로의 크기를 입력받고, 그에 따라 2차원 배열인 maze를 초기화합니다. 각 행을 읽어 들여 0과 1로 나누어 저장합니다.

6.2. BFS 함수

BFS 함수에서는 큐를 사용하여 현재 위치에서 4방향으로 이동할 수 있는지를 검사합니다. 여기에서는 deltaRow와 deltaCol 배열을 사용하여 상하좌우로 이동할 때의 인덱스를 계산합니다.

6.3. 경로 Counting

도착점에 도달했을 경우, pathCount를 증가시키며 다른 경로를 탐색할 수 있도록 관리합니다. BFS는 모든 가능한 경로를 탐색하는 데 유용한 방법입니다.

7. 성능 분석

이 알고리즘의 시간 복잡도는 O(N * M)입니다. 이는 각 셀을 한 번씩 체크하기 때문입니다. 그러나 최악의 경우 모든 경로를 탐색해야 하므로 추가적인 시간 소모가 있을 수 있습니다.

8. 문제 해결 후 한 단계 더 나아가기

이제 미로 탐색의 기본적인 개념을 이해했으니, 다음 단계로 미로의 최단 경로를 계산할 수 있는 Dijkstra 알고리즘이나 A* 알고리즘을 활용해 보세요. 각 알고리즘의 작동 방식을 학습하고, 이를 활용하여 최적 경로 문제를 해결하는 데 도전해 보세요.

9. 마무리

이번 강좌에서는 C#을 이용한 미로 탐색 문제를 해결하는 방법을 알아보았습니다. BFS 알고리즘이 어떻게 동작하는지, 그리고 문제를 해결하기 위해 어떤 과정을 거쳤는지를 살펴보았습니다. 이번 강좌가 여러분의 알고리즘 실력 향상에 도움이 되었기를 바라며, 더 많은 코딩테스트 준비를 진행하시기 바랍니다.