[C#]TopCoder 알고리즘 트레이닝 : 미로 만드는 사람

---

• 문제

입력

 

---

• 문제풀이

기본적으로 BFS(넓이우선탐색)을 사용하였다. 큐에 넣고 조건에 맞다면 dx, dy에 의해 지정된칸으로 이동후 다시 탐색과정을 거친다. 최종적으로 가장높은 숫자가 미로의 출구이다.

---

• 코드 1

using System;
using System.Collections.Generic;

class Program
{
    public static int[,] graph = new int[50, 50];
    public static int[] dx = { -1, 1, 0, 0, 1, 1, -1, -1 };
    public static int[] dy = { 0, 0, 1, -1, 1, -1, -1, 1 };
    public static int[] moveRow;
    public static int[] moveCol;
    public static string[] maze;
    public static Queue<(int, int)> queue = new Queue<(int, int)>();
    public static int num;

    static void Main(string[] args)
    {
        string[] maze = {
            ".......",
            "X.X.X..",
            ".......",
            "....X..",
            "X....X.",
            "......."
            /*"...",
            "...",
            "..."*/
            /*"X.X",
            "...",
            "XXX",
            "X.X"*/
            //"..X.X.X.X.X.X."
        };

        int startRow = 5;
        int startCol = 0;
        int[] moveRow = new int[] { 1, 0, -1, 0, -2, 1 };
        int[] moveCol = new int[] { 0, -1, 0, 1, 3, 0 };

        for (int i = 0; i < maze.Length; i++)
        {
            for (int j = 0; j < maze[0].Length; j++)
            {
                graph[i, j] = -1;
            }
        }

        graph[startRow, startCol] = 0;
        queue.Enqueue((startRow, startCol));

        while (queue.Count > 0)
        {
            (int a, int b) = queue.Dequeue();

            for (int k = 0; k < moveRow.Length; k++)
            {
                int y = a + moveRow[k];
                int x = b + moveCol[k];
                if (y >= 0 && y < maze.Length && x >= 0 && x < maze[0].Length)
                {
                    if (maze[y][x] == '.' && graph[y, x] == -1)
                    {
                        graph[y, x] = graph[a, b] + 1;
                        queue.Enqueue((y, x));
                    }
                }
            }
        }

        /* 확인하기
        for (int i = 0; i < maze.Length; i++)
        {
            for (int j = 0; j < maze[0].Length; j++)
            {
                if (i == startRow && j == startCol)
                {
                    Console.Write($"{"start",-6}");
                }
                else Console.Write($"{graph[i, j],-6}");
            }
            Console.WriteLine();
        }
        */
        num = 0;
        for (int i = 0; i < maze.Length; i++)
        {
            for (int j = 0; j < maze[0].Length; j++)
            {
                if (maze[i].Substring(j, 1) == "." && graph[i, j] == -1)
                {
                    num = -1;
                    break;
                }
                num = Math.Max(num, graph[i, j]);
            }
        }

        Console.WriteLine(num);
    }
}

---

• 후기

오랜만에 BFS를 했더니 행과 열을 반대로 더해야한다는 것을 까먹었다.