[ BOJ/C# ] 2178 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

이번에도 BFS 문제이다. 

이번에도 Queue 2개로 문제를 해결하였는데, 이동 가능한 길이 2개 이상일 경우 때문이다. 

처음에 메모리 초과가 떴는데, visited 방문 리스트를 체크해 주는 지점을 제대로 설정하지 않아서 생긴 문제였다. 

using System;
using System.IO;

namespace B2178
{
    class Program
    {
        static int N, M;
        static int min = 1;
        static int[,] map = new int[101, 101];
        static bool[,] visited = new bool[101, 101];
        static Queue<(int, int)> q = new Queue<(int, int)>();
        static Queue<(int, int)> qs = new Queue<(int, int)>();
        static int[] dx = { -1, 1, 0, 0 };
        static int[] dy = { 0, 0, -1, 1 };
        static bool isDone = false;
        static void BFS()
        {
            min++;
            if (q.Count > 0)
            {
                while (q.Count > 0)
                {
                    var deq = q.Dequeue();
                    int deqx = deq.Item1;
                    int deqy = deq.Item2;
                    visited[deqx, deqy] = true;
                    for (int i = 0; i < 4; i++)
                    {
                        deqx = deq.Item1 + dx[i];
                        deqy = deq.Item2 + dy[i];
                        if (deqx < 0 || deqy < 0 || deqx >= N || deqy >= M || visited[deqx, deqy] == true)
                            continue;
                        visited[deqx, deqy] = true;
                        if (deqx == N - 1 && deqy == M - 1)
                        {
                            isDone = true;
                            return;
                        }
                        if (map[deqx, deqy] == 1)
                        {
                            qs.Enqueue((deqx, deqy));
                        }
                    }
                }
            }
            else if (qs.Count > 0)
            {
                while (qs.Count > 0)
                {
                    var deq = qs.Dequeue();
                    int deqx = deq.Item1;
                    int deqy = deq.Item2;
                    visited[deqx, deqy] = true;
                    for (int i = 0; i < 4; i++)
                    {
                        deqx = deq.Item1 + dx[i];
                        deqy = deq.Item2 + dy[i];
                        if (deqx == N - 1 && deqy == M - 1)
                        {
                            isDone = true;
                            return;
                        }
                        if (deqx < 0 || deqy < 0 || deqx >= N || deqy >= M) continue;
                        if (map[deqx, deqy] == 1 && visited[deqx, deqy] == false)
                        {
                            q.Enqueue((deqx, deqy));
                        }
                    }
                }
            }
        }
        static void Main()
        {
            StreamReader sr = new StreamReader((Console.OpenStandardInput()));
            StreamWriter sw = new StreamWriter((Console.OpenStandardOutput()));
            int[] nm = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            N = nm[0];
            M = nm[1];
            for(int i = 0; i < N; i++)
            {
                string str = sr.ReadLine();
                for (int j = 0; j < M; j++)
                    map[i, j] = (int)str[j] - 48;
            }
            q.Enqueue((0, 0));
            while (isDone == false) BFS();
            sw.Write(min);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}