[프로그래머스 C#] Lv.2 리코쳇 로봇

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

프로그래머스

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

- 이동 시에 벽을 만나거나 범위를 벗어날때까지 같은 방향으로 이동해야 함

- 최단거리 찾기 문제이므로 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[] board)
        {
            var dirY = new int[4] { 1, -1, 0, 0 };
            var dirX = new int[4] { 0, 0, 1, -1 };
            var boolArray = new bool[board.Length, board[0].Length];
            var queue = new Queue<Pos>();

            // 시작 좌표 가져오기
            var startPoint = FindPos(board, 'R');

            // 시작점 세팅
            queue.Enqueue(new Pos(startPoint.Item1, startPoint.Item2, 0));
            boolArray[startPoint.Item1, startPoint.Item2] = true;

            // BFS 탐색
            while (queue.Count > 0)
            {
                Pos currPos = queue.Dequeue();

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

                    // 이동 (미끄러지기)
                    while (true)
                    {
                        movePos.y += dirY[i];
                        movePos.x += dirX[i];

                        // 범위 벗어남 or 벽을 만남
                        if (movePos.y < 0 || movePos.y >= board.Length ||
                           movePos.x < 0 || movePos.x >= board[0].Length ||
                           board[movePos.y][movePos.x] == 'D')
                        {
                            movePos.y -= dirY[i];
                            movePos.x -= dirX[i];
                            break;
                        }
                    }

                    // 도착했다면
                    if (board[movePos.y][movePos.x] == 'G')
                        return movePos.moveCount;

                    // 방문했던 좌표가 아니라면 탐색 대상
                    if (boolArray[movePos.y, movePos.x] == false)
                    {
                        boolArray[movePos.y, movePos.x] = true;
                        queue.Enqueue(movePos);
                    }
                }
            }

            // 갈 수 있는 모든 경우를 체크했는데 도착하지 못했다면
            return -1;
        }

        // 찾는 문자의 (y, x) 좌표를 찾아서 반환
        public (int, int) FindPos(string[] board, Char findChar)
        {
            for (int i = 0; i < board.Length; i++)
            {
                int num = board[i].IndexOf(findChar);

                if (num != -1)
                    return (i, num);
            }

            return (-1, -1);
        }
    }