미로 탐색

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

192 MB

194425

88564

56325

44.038%

문제

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)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

예제 입력 4

예제 출력 4

이 문제 볼때 바로 너비우선탐색을 이용해서 풀면되겠다 싶었다.
그래서 바로 코드를 뚝딱 만들고 제출을 해보니 메모리초과가 나는것이였다.
하지만 처음에 디버깅을 돌릴때 왜 자꾸 같은 좌표가 큐에 넣어지는거지? 이러면 안되는데라고 생각을했는데 어차피 답은 나오니깐 상관없겠지라고 생각한 내가 바보였다.
결국 여기 부분에서 메모리초과가 나는것이였다.
너비우선탐색인데도 틀렸던 이유가 방문 체크를 하는 방법이 잘못됐던거였다 나는 그냥 그 좌표에 진입했을때 방문체크를 했는데 이래버리면 이미 큐에 저장되있던 좌표들이 또 그 좌표를 또 방문하게 될수도 있는것이였다.

그래서 그 미로는 진입이 가능한 미로일때 바로 방문체크를 하였고 이렇게하면 먼저 큐에있던 노드들이 이미 방문한 노드들을 가지않으니깐 더 빠른 탐색이 가능해진다.

이렇게해서 제출하니깐 바로 정답이 나왔다.

괜히 dp로 풀어야되나? 라고 생각한 내가 바보였다.

dp규칙을 찾을려했는데 중간에 0이섞인 미로도 있기때문에 바로 dp가 아니구나 했다 ㅎㅎ;;

내가 푼 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Prob2178_미로탐색BFS
{
    class Node
    {
        public int X { get; set; }
        public int Y { get; set; }

        public int Cost { get; set; }

        public Node(int x, int y, int cost)
        {
            X = x;
            Y = y;
            Cost = cost;
        }

    }
    class Program
    {
        static int[,] maps;
        static bool[,] visited;
        static int[] xCost = { 0, 0, -1, 1 };
        static int[] yCost = { -1, 1, 0, 0 };    
        static int BFS(int n, int m)
        {
            Queue<Node> queue = new Queue<Node>();

            queue.Enqueue(new Node(1, 1, 1));

            visited[1, 1] = true;

            while (queue.Count != 0)
            {
                Node currentNode = queue.Dequeue();
                int x = currentNode.X;
                int y = currentNode.Y;
                int cost = currentNode.Cost;
           
                for (int i = 0; i < 4; i++)
                {
                    if (y + yCost[i] == n && x + xCost[i] == m)
                    {                      
                        cost++;
                        return cost;
                    }
                    else if(maps[y + yCost[i], x + xCost[i]] != 0 &&
                            !visited[y + yCost[i], x + xCost[i]])
                    {                        
                        queue.Enqueue(new Node(x + xCost[i], y + yCost[i], cost + 1));
                        visited[y + yCost[i], x + xCost[i]] = true;
                    }
                }
             
            }

            return default;
        }
        static void Main(string[] args)
        {
            string[] arr = Console.ReadLine().Split();

            int n = int.Parse(arr[0]);
            int m = int.Parse(arr[1]);

            maps = new int[n + 2, m + 2];
            visited = new bool[n + 2, m + 2];

            for (int i = 1; i < n + 1; i++)
            {
                string map = Console.ReadLine();

                for(int j = 1; j < m + 1; j++)
                {
                    maps[i, j] = int.Parse(map[j - 1].ToString());
                }
            }

            int count = BFS(n, m);
            Console.WriteLine(count);
        }
    }
}