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

프로그래머스 - 미로 탈출 문제입니다.(링크)

문제 설명은 프로그래머스에서 확인해주세요.

접근 방법 - BFS

탐색 문제이기 때문에 문제 접근을 BFS로 했는데 이유는 DFS보다 BFS가 디버깅하기 쉽기 때문이다.

DFS는 재귀.. 재귀는 디버깅이 쉽지 않다. 그래서 개인적으로 선호하지 않는다.

주의 사항

방문한 노드 관리

문제의 제한 사항을 보면 아래의 내용을 볼 수 있다.

출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

이게 가장 중요한 내용이라 생각하는데 보통 탐색을 할 때 방문한 노드는 재방문하지 않게 처리하고 있다.
하지만 제한 사항을 보면 여러 번 지나갈 수 있다고 했기에 방문한 노드 관리는 탐색마다 다르게 관리해주어야 한다.

통로를 지나갈 때만 시간이 느는 것이 아니다.

문제를 풀면서 놓친 케이스인데 문제 설명을 보면 아래와 같은 내용이 있다.

이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.

즉,
통로인 O를 지나갈 때만 시간을 +1 해주는 것이 아니라 목표 지점까지 가는 동안 X를 제외한 모든 곳을 지날 때 시간을 +1 해주어야 한다.

에를 들어, 아래와 같은 테스트 케이스가 있다고 가정하자.

테스트 케이스로는 [“SLX”,”EXX”]

테스트 케이스 결과로는

• 시작 지점에서 레버로 이동(S -> L): 1회
• 레버에서 출구로 이동(L -> E): 2회 로 총 3 이라는 시간이 걸리게 된다.

하지만 그 사이에는 통로(O)는 존재하지 않는다.
그렇기 때문에 목표 지점까지 가는 동안 벽(X)을 제외한 모든 곳을 지날 때 +1씩 해주어야 한다.

코드

이제 주의 사항까지 살펴보았으니 문제를 풀어보자.

시작하기 앞서,
파라미터 값이 string[]이라서 이해하기 쉽게 ValueTuple로 row col 을 표현하여 접근했다.

위의 설명 + 코드만 있어도 이해할 수 있다고 생각해 세부적인 구현 설명은 생략하였습니다.

using System;
using System.Collections.Generic;

public class Solution
{
    bool IsStart(char value) => value == 'S';
    bool IsExit(char value) => value == 'E';
    bool IsLabber(char value) => value == 'L';
    bool IsPath(char value) => value == 'O';
    bool IsBlock(char value) => value == 'X';

    (int row,int col) GetTargetPos(string[] maps, Func<char,bool> targetComarer)
    {
        (int row, int col)  result = (-1, -1);

        if (maps == null || targetComarer == null)
            return result;

        for (int i = 0; i < maps.Length; i++)
        {
            for (int j = 0; j < maps[i].Length; j++)
            {
                if (targetComarer(maps[i][j]))
                {
                    result = (i, j);
                    return result;
                }
            }
        }

        return result;
    }

    int GetTimeByMovementToTarget(string[] maps,Predicate<char> isTargetPredic,(int row,int col) startingPos)
    {
        if (maps == null || isTargetPredic == null)
            return -1;

        Queue<(int row, int col, int time)> queue = new Queue<(int row, int col, int time)>();
        HashSet<(int row, int col)> visited = new HashSet<(int row, int col)>();

        int time = -1;

        queue.Enqueue((startingPos.row, startingPos.col, -1));

        while (queue.Count > 0)
        {
            var el = queue.Dequeue();

            if (el.row < 0 || el.col < 0)
                continue;

            if (el.row >= maps.Length || el.col >= maps[el.row].Length)
                continue;

            if (!visited.Add((el.row,el.col)))
                continue;

            if (IsBlock(maps[el.row][el.col]))
                continue;

            el.time += 1;

            if (isTargetPredic(maps[el.row][el.col]))
            {
                if (time == -1)
                    time = el.time;
                else
                    time = Math.Min(time, el.time);
            }

            (int row, int col, int time) behind = (el.row, el.col - 1, el.time);
            (int row, int col, int time) up = (el.row + 1, el.col, el.time);
            (int row, int col, int time) front = (el.row, el.col + 1, el.time);
            (int row, int col, int time) down = (el.row - 1, el.col, el.time);

            queue.Enqueue(behind);
            queue.Enqueue(up);
            queue.Enqueue(front);
            queue.Enqueue(down);

        }

        return time;
    }

    public int solution(string[] maps)
    {
        if (maps == null)
            return -1;

        int answer = 0;

        var startingPoint = GetTargetPos(maps, IsStart);
        var labberPoint = GetTargetPos(maps, IsLabber);

        if (startingPoint.row == -1 || startingPoint.col == -1)
            return -1;

        if (labberPoint.row == -1 || labberPoint.col == -1)
            return -1;

        var result = GetTimeByMovementToTarget(maps, IsLabber, startingPoint);
        if (result == -1)
            return -1;

        answer += result;

        result = GetTimeByMovementToTarget(maps, IsExit, labberPoint);
        if (result == -1)
            return -1;

        answer += result;

        return answer;
    }
}