[프로그래머스] 미로 탈출

1. 문제

미로 탈출

2. 개요

1 x 1 크기의 칸들로 이루어진 직사각형 형태의 미로를 탈출하려고 한다. 각 칸은 통로나 벽으로 구성되어있고 통로로 된 칸으로만 이동이 가능하다.

통로들 중에는 레버와 탈출구가 있는데, 탈출구로 탈출하기 위해서는 먼저 레버가 있는 곳으로 가서 레버를 당겨야만 한다.

미로의 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는 데 걸리는 시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

주어진 지도를 확인하여 시작 위치, 레버의 위치, 탈출구의 위치를 파악해 놓는다.

이후 BFS를 이용하여 시작 위치부터 레버까지의 최소 거리와 레버부터 탈출구까지의 최소 거리를 각각 구한다.

만약 둘 중 하나라도 도착이 불가능하다면 -1을, 그렇지않다면 두 거리의 합을 리턴한다.

3-2. C#

using System;
using System.Collections.Generic;

public class Solution {
    static int mapH;
    static int mapW;
    
    public int solution(string[] maps) {
        int[] start = new int[2];
        int[] lever = new int[2];
        int[] dest = new int[2];

        mapH = maps.Length;
        mapW = maps[0].Length;

        for (int i = 0; i < mapH; i++)
        {
            for (int j = 0; j < mapW; j++)
            {
                if (maps[i][j] == 'S')
                {
                    start[0] = i;
                    start[1] = j;
                }

                else if (maps[i][j] == 'E')
                {
                    dest[0] = i;
                    dest[1] = j;
                }

                else if (maps[i][j] == 'L')
                {
                    lever[0] = i;
                    lever[1] = j;
                }
            }
        }

        int startToLever = BFS(start[0], start[1], lever[0], lever[1], maps);
        int leverToDest = BFS(lever[0], lever[1], dest[0], dest[1], maps);

        int answer = (startToLever != 0 && leverToDest != 0) ? startToLever + leverToDest : -1;
        return answer;
    }

    public int BFS(int y, int x, int destY, int destX, string[] maps)
    {
        int[] dirY = { -1, 0, 1, 0 };
        int[] dirX = { 0, -1, 0, 1 };

        int[,] visited = new int[mapH, mapW];

        Queue<int[]> q = new Queue<int[]>();
        q.Enqueue(new int[] { y, x });

        while (q.Count > 0 && visited[destY, destX] == 0)
        {
            int[] now = q.Dequeue();
            int nowY = now[0];
            int nowX = now[1];

            for (int i = 0; i < 4; i++)
            {
                int nextY = nowY + dirY[i];
                int nextX = nowX + dirX[i];

                if (nextY < 0 || nextY >= mapH || nextX < 0 || nextX >= mapW)
                    continue;

                if (maps[nextY][nextX] == 'X')
                    continue;

                if (visited[nextY, nextX] != 0)
                    continue;

                visited[nextY, nextX] = visited[nowY, nowX] + 1;
                q.Enqueue(new int[] { nextY, nextX });
            }

        }

        return visited[destY, destX];
    }
}