[C#] 백준 2178번 미로 탐색

[ 문제 ]

N×M크기의 배열로 표현되는 미로가 있다.

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

 

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

[ 코드 ]

class Program
{
    static int n, m;
    static int[,] graph;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    static void Main()
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        string[] input = sr.ReadLine().Split();
        n = int.Parse(input[0]);
        m = int.Parse(input[1]);

        graph = new int[n, m];

        for (int i = 0; i < n; i++)
        {
            string line = sr.ReadLine().Trim();
            for (int j = 0; j < m; j++)
            {
                graph[i, j] = line[j] - '0';
            }
        }

        sw.Write(BFS(0, 0));
        sw.Flush();
        sw.Close();
        sr.Close();
    }

    static int BFS(int x, int y)
    {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((x, y));

        while (queue.Count > 0)
        {
            (int cx, int cy) = queue.Dequeue();

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

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && graph[nx, ny] == 1)
                {
                    queue.Enqueue((nx, ny));
                    graph[nx, ny] = graph[cx, cy] + 1;
                }
            }
        }

        return graph[n - 1, m - 1];
    }
}

 

[ 실행화면 ]

case: 1

case: 2

case: 3

case: 4

 

 

 

 

 

---

문제링크: https://www.acmicpc.net/problem/2178