[C#] 백준 2178번 문제풀이

문제번호: 2178

문제명: 미로 탐색

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

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

오늘은 BFS를 사용한 미로탐색 문제를 풀었습니다.
BFS 구현 원리는 큐를 만들어서 더 갈곳이 없거나 목적지에 도착할때까지 이동하고 visited 이중 bool배열을 이용하여 이미 이동한곳은 건너뛰도록 했습니다. 또한 이동할 수 있는 방향을 { 1, -1, 0, 0 }, { 0, 0, 1, -1 } 와 같이 입력해두고 사용하였습니다.
다음은 정답코드입니다.

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

    int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse); // 0과 1로 채워져있는 미로. 1은 갈 수 있고 0은 갈 수 없다. NM위치에 도달하기 위한 BFS 설계해야함.
    int N = NM[0]; // y
    int M = NM[1]; // x

    int[,] graph = new int[N, M];
    bool[,] visited = new bool[N, M];
    int[] dx = { 1, -1, 0, 0 };
    int[] dy = { 0, 0, 1, -1 };   

    for (int i = 0; i < N; i++)
    {
        string input = sr.ReadLine()!;
        for (int j = 0; j < M; j++)
        {
            graph[i, j] = input[j] - '0';
        }
    }

    sw.WriteLine(BFS());

    int BFS()
    {
        Queue<(int x, int y, int dist)> q = new Queue<(int, int, int)>();

        q.Enqueue((0, 0, 1));
        visited[0, 0] = true;

        while(q.Count > 0)
        {
            var (x, y, dist ) = q.Dequeue();
            if (x == N - 1 && y == M - 1)
                return dist;

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;

                if (!visited[nx, ny] && graph[nx, ny] == 1)
                {
                    visited[nx, ny] = true;
                    q.Enqueue((nx, ny, dist + 1));
                }
            }
        }

        return -1;
    }
}