C# 코딩테스트 강좌, 경로 찾기

안녕하세요! 이번 글에서는 코딩테스트에서 자주 등장하는 알고리즘 문제 중 하나인 경로 찾기 문제를 다뤄보겠습니다. 이 강좌에서는 문제의 정의, 해법, C# 코드 구현 등을 자세히 설명하겠습니다. 문제를 해결하기 위해 필요한 알고리즘의 기초부터 시작하여, 복잡한 경로 탐색 알고리즘을 적용하는 방법까지 알아보도록 하겠습니다.

문제 정의

문제는 다음과 같습니다:

주어진 2차원 grid에서 시작점 S에서 도착점 E까지의 최단 경로를 찾으세요. grid는 0과 1로 이루어져 있으며, 0은 이동 가능한 칸, 1은 벽을 의미합니다. 경로는 상하좌우 인접한 칸으로만 이동할 수 있습니다. 경로가 존재하는 경우, 최단 경로의 길이를 반환하고, 존재하지 않는 경우 -1을 반환하세요.

예제

다음은 예제 입력과 출력입니다:

입력:
grid = [
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 1],
  [0, 1, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [1, 1, 1, 1, 0]
]
start = (0, 0)  // S의 위치
end = (4, 4)    // E의 위치

출력:
최단 경로의 길이 = 8

문제 해결 접근

문제를 해결하기 위해 다양한 방법이 있지만, BFS (너비 우선 탐색) 알고리즘을 사용할 것입니다. BFS는 최단 경로 문제를 해결하는 데 매우 효과적인 방법입니다. BFS는 현재 노드와 인접한 노드를 차례로 탐색하고, 모든 노드를 탐색한 후 최단 경로를 반환합니다.

알고리즘 설명

BFS 알고리즘의 기본 구조는 다음과 같습니다:

시작점을 큐에 넣고, 방문 체크를 합니다.
큐가 비어있지 않은 동안 반복합니다:

큐에서 현재 위치를 꺼냅니다.
현재 위치가 도착점이라면 최단 경로의 길이를 반환합니다.
현재 위치와 인접한 모든 칸을 확인합니다:

이동 가능한 칸이면서 방문하지 않은 칸이라면, 큐에 추가하고 방문 체크를 합니다.

모든 경로를 탐색한 후에도 도착점에 도달하지 못하면 -1을 반환합니다.

C# 코드 구현

이제 위에서 설명한 알고리즘을 C# 코드로 구현해 보겠습니다.


using System;
using System.Collections.Generic;

class Program {
    public static int ShortestPath(int[,] grid, (int, int) start, (int, int) end) {
        int rows = grid.GetLength(0);
        int cols = grid.GetLength(1);
        
        int[] directions = {0, 1, 0, -1, 0}; // 상하좌우 이동

        Queue<((int, int), int)> queue = new Queue<((int, int), int)>();
        bool[,] visited = new bool[rows, cols];
        
        queue.Enqueue((start, 0)); // (위치, 경로의 길이)
        visited[start.Item1, start.Item2] = true;

        while (queue.Count > 0) {
            var (current, length) = queue.Dequeue();

            if (current == end) {
                return length;
            }

            for (int i = 0; i < 4; i++) {
                int newRow = current.Item1 + directions[i];
                int newCol = current.Item2 + directions[i + 1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && 
                    grid[newRow, newCol] == 0 && !visited[newRow, newCol]) {
                    
                    queue.Enqueue(((newRow, newCol), length + 1));
                    visited[newRow, newCol] = true;
                }
            }
        }

        return -1; // 도착점에 도달할 수 없는 경우
    }

    public static void Main() {
        int[,] grid = {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 1},
            {0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {1, 1, 1, 1, 0}
        };
        
        var start = (0, 0);
        var end = (4, 4);
        int result = ShortestPath(grid, start, end);
        Console.WriteLine("최단 경로의 길이: " + result);
    }
}

코드 리뷰

위의 코드는 BFS 알고리즘을 사용하여 경로를 찾는 방법을 보여줍니다. 코드의 각 부분을 자세히 살펴보겠습니다.

변수 설명

rows와 cols: grid의 행과 열의 수를 저장합니다.
directions: 상하좌우로 이동하기 위한 방향을 정의합니다.
queue: BFS를 위한 큐입니다. (위치, 경로의 길이) 쌍을 저장합니다.
visited: 각 칸의 방문 여부를 체크하는 2D 배열입니다.

큐의 작동

큐에서 현재 위치를 꺼내고, 모든 인접한 칸을 확인하여 이동 가능한 경우 큐에 추가합니다. 이 과정이 반복되면서 최단 경로를 찾습니다.

성능 분석

이 알고리즘의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수(2D grid의 모든 칸)이고 E는 간선의 수(상하좌우 인접한 칸의 수)에 해당합니다. 공간 복잡도는 O(V)로, BFS를 하기 위한 큐와 방문 체크에 필요한 공간을 차지합니다.

결론

이번 글에서는 C#을 사용하여 경로 찾기 문제를 다뤘습니다. BFS 알고리즘을 활용하여 최단 경로를 찾는 과정을 설명하였고, 이를 코드로 구현해 보았습니다. 이처럼 알고리즘 문제를 풀 때는 문제를 정확히 이해하고, 적절한 알고리즘을 선택하여 접근하는 것이 중요합니다. 여러분도 다양한 문제를 통해 실력을 향상시킬 수 있기를 바랍니다!

감사합니다!