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

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

최단거리 길찾기를 조건에 따라 두번 적용하면 되는 문제 ( S -> L / L -> E )

 

- 현재 위치와 누적이동횟수를 class Pos를 선언해서 각 좌표와 누적이동횟수를 나타냄

 

- 주어진 maps로 벽, 도착지점을 판단하고, 방문배열을 따로 선언해 지나온 길을 체크함

 

- 최단 거리를 구하는 문제이므로 BFS(너비 우선 탐색) 알고리즘 적용

https://godgjwnsgur7.tistory.com/47 

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public class Pos
        {
            public int y;
            public int x;
            public int moveCount;

            public Pos(int y, int x, int moveCount)
            {
                this.y = y;
                this.x = x;
                this.moveCount = moveCount;
            }
        }

        public int solution(string[] maps)
        {
            int answer = 0;
            Pos startPos = FindChar(maps, 'S');
            Pos leverPos = FindChar(maps, 'L');

            // S -> L
            int moveCount1 = Function(maps, startPos, 'L');
            int moveCount2 = -1;

            // L -> E
            if (moveCount1 != -1)
                moveCount2 = Function(maps, leverPos, 'E');
            
            // 길이 존재한다면 answer에 값 세팅
            if (moveCount2 != -1)
                answer = moveCount1 + moveCount2;

            return answer;
        }

        // maps에서 문자에 해당하는 y, x 좌표 값을 반환하는 메서드
        public Pos FindChar(string[] maps, Char findChar)
        {
            Pos pos = new Pos(0, 0, 0);

            for (pos.y = 0; pos.y < maps.Length; pos.y++)
            {
                pos.x = maps[pos.y].IndexOf(findChar);
                if (pos.x > -1) break;
            }

            return pos;
        }

        // 시작 -> 도착 지점까지의 최단거리를 반환하는 메서드
        public int Function(string[] maps, Pos startPos, Char findChar)
        {
            var boolArrays = new bool[maps.Length, maps[0].Length]; // 방문배열
            var dirY = new int[4] { 1, -1, 0, 0 };
            var dirX = new int[4] { 0, 0, 1, -1 };

            var queue = new Queue<Pos>();
            queue.Enqueue(startPos);
            
            // BFS 탐색
            while (queue.Count > 0)
            {
                Pos currPos = queue.Dequeue();

                for (int i = 0; i < 4; i++)
                {
                    Pos movePos = new Pos(currPos.y + dirY[i], currPos.x + dirX[i], currPos.moveCount + 1);

                    // 범위를 벗어났거나, 벽인 경우
                    if (movePos.y < 0 || movePos.y >= maps.Length ||
                       movePos.x < 0 || movePos.x >= maps[0].Length)
                        continue;

                    // 벽이거나, 이미 탐색된 길이라면
                    if (maps[movePos.y][movePos.x] == 'X' || boolArrays[movePos.y, movePos.x])
                        continue;

                    // 목표 지점 도착
                    if (maps[movePos.y][movePos.x] == findChar)
                        return movePos.moveCount;
                    
                    boolArrays[movePos.y, movePos.x] = true;
                    queue.Enqueue(movePos);
                }
            }

            return -1;
        }
    }