[프로그래머스 C#] Lv.3 미로 탈출 명령어

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

프로그래머스

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

주어진 문제의 x, y 값을 좌표계로 보고 접근 ( x, y 값이 정확히 무엇을 의미하는지 정확히 파악해야 함 )

- 이동 우선순위는 아래 d(x++) -> 왼쪽 l(y--) -> 오른쪽 r(y++) -> 위 u(x--)

 

+ 문제 예시는 마치 유사 완전탐색을 해야하는 문제처럼 예시를 들고 있지만, 명확한 이동 우선순위 등의 조건이 있기 때문에, 완전탐색보다는 필요한 값을 찾는 게 맞다고  판단함

 

1) 가능한 조건인지 판단

- 이동 가능 거리인 k 값보다 최소 이동거리가 클 경우

- 이동 가능 횟수와 거리는 둘다 짝수이거나 둘다 홀수여야 이동이 가능함 ( 딱 맞게 도착 )

 

2) 최단 거리로 이동할 필요가 없는 경우 먼저 처리

- 최단거리와 이동 가능 횟수를 비교해 똑같다면 우선순위보다 최단거리이동이 우선이 됨

 ( 단, 반복문 1사이클에선 단 1번의 이동만 있어야 함 )

 

3) 최단 거리로 이동

- 2번에서 최소 이동 거리와 현재 이동 가능 횟수가 같은지 판단하여 최단거리 이동을 우선순위에 맞게 함

 

+ 이동할 때마다 문자열에 추가가 일어나므로 StringBuilder 사용

 

주석 참조

    using System;
    using System.Text;

    public class Solution
    {
        public enum ENUM_DIR { d = 0, l = 1, r = 2, u = 3 };
        
        public string solution(int n, int m, int x, int y, int r, int c, int k)
        {
            // d(x++) -> l(y--) -> r(y++) -> u(x--)

            var sb = new StringBuilder();
            // 각 방향을 담은 dirY, dirX
            int[] dirY = new int[4] { 0, -1, 1, 0 };
            int[] dirX = new int[4] { 1, 0, 0, -1 };

            // 1.이동할 수 없는 조건 (딱 맞게 도착 불가능, 최단거리보다 이동가능 횟수가 적은 경우)
            if ((GetMinDirection(x, y, r, c) % 2 == 0) != (k % 2 == 0)
                || GetMinDirection(x, y, r, c) > k)
                return "impossible";

            // 2. 최단거리가 될 때까지 이동
            while (GetMinDirection(x, y, r, c) != k && k > 0)
            {
                k--; // 이동 카운트 ( 무조건 이동할 것 )

                for (int i = 0; i < 4; i++)
                {
                    x += dirX[i];
                    y += dirY[i];

                    // 우선순위대로 이동이 가능하다면 이동
                    if (x > 0 && y > 0 && x <= n && y <= m)
                    {
                        sb.Append(((ENUM_DIR)i).ToString());
                        break;
                    }
                    else // 이동이 불가능하다면 값을 되돌림
                    {
                        x -= dirX[i];
                        y -= dirY[i];
                    }
                }
            }

            // 3. 최단거리 이동
            while (x != r || y != c)
            {
                k--; // 이동 카운트 ( 무조건 이동할 것 )

                for (int i = 0; i < 4; i++)
                {
                    x += dirX[i];
                    y += dirY[i];

                    // 우선순위 순서대로 최단거리 이동
                    if (x > 0 && y > 0 && x <= n && y <= m
                      && GetMinDirection(x, y, r, c) == k)
                    {
                        sb.Append(((ENUM_DIR)i).ToString());
                        break;
                    }
                    else // 이동이 불가능하다면 값을 되돌림
                    {
                        x -= dirX[i];
                        y -= dirY[i];
                    }
                }

            }

            return sb.ToString();
        }

        // (x,y) <-> (r,c) 최소 거리를 반환하는 메서드
        public int GetMinDirection(int x, int y, int r, int c)
        {
            return Math.Abs(x - r) + Math.Abs(y - c);
        }
    }