[프로그래머스 C#] Lv.3 아이템 줍기

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

프로그래머스

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

다각형 범위의 테두리로만 이동할 수 있을 때, 목적지까지의 최소 이동 거리를 구하는 문제

다각형은 주어진 사각형 영역을 모두 합친 모양

 

1) 다각형의 테두리 구하기

- 구하려는 다각형의 테두리와 테두리 안쪽을 나타내는 2차원 int배열을 선언

 -> 0 : 다각형 범위를 벗어난 영역 ( 이동 불가능 )

 -> 1 : 다각형의 테두리 영역 ( 이동 가능 )

 -> 2 : 다각형의 테두리 안쪽 영역 ( 이동 불가능 )

 

- 사각형 영역의 테두리 안쪽은 무조건 2로 세팅 ( 무조건 다각형의 테두리 안쪽이 됨 )

- 사각형 영역의 테두리는 다각형의 테두리 안쪽이 아니라면 다각형의 테두리가 됨

 

+ 만약 주어진 사각형 영역의 한 변의 길이가 1일 경우에 테두리가 아닌 테두리 안쪽을 지나갈 수 있게 되므로 모든 포지션 관련된 값을 2로 곱하여 길이가 1인 사각형의 테두리 안쪽을 표현할 수 있게 함

 

2) 최소 이동 거리 구하기

- 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 count;

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

        public int solution(int[,] rectangle, int characterX, int characterY, int itemX, int itemY)
        {
            int answer = 0;
            // 다각형의 테두리 1 (갈 수 있음), 다각형의 테두리 안쪽 2 (갈 수 없음)
            var intArrays = new int[102, 102]; 
            
            // 한 변의 길이가 1인 사각형에 대응하기 위해 모든 좌표를 *2로 둠
            characterY *= 2;
            characterX *= 2;
            itemY *= 2;
            itemX *= 2;
            
            // 각 사각형 영역을 탐색해 다각형의 테두리와 내부를 구함
            for (int i = 0; i < rectangle.GetLength(0); i++)
            {
                // 모든 좌표 * 2
                int startPosY = rectangle[i, 1] * 2;
                int startPosX = rectangle[i, 0] * 2;
                int endPosY = rectangle[i, 3] * 2;
                int endPosX = rectangle[i, 2] * 2;

                // 현재 탐색하는 사각형의 영역 탐색
                for (int y = startPosY; y <= endPosY; y++)
                {
                    for (int x = startPosX; x <= endPosX; x++)
                    {
                        // 테두리인 경우
                        if (y == startPosY || y == endPosY || x == startPosX || x == endPosX)
                        {
                            // 다른 사각형의 테두리 안쪽이 아닌 경우에만 갈 수 있는 길로 체크
                            if (intArrays[y, x] != 2)
                            {
                                intArrays[y, x] = 1;
                                continue;
                            }
                        }

                        // 테두리 안쪽인 경우
                        intArrays[y, x] = 2; 
                    }
                }
            }

            var queue = new Queue<Pos>();
            var dirY = new int[4] { 0, 0, 1, -1 };
            var dirX = new int[4] { 1, -1, 0, 0 };
            queue.Enqueue(new Pos(characterY, characterX, 0));

            // BFS 탐색
            while (queue.Count > 0)
            {
                Pos currPos = queue.Dequeue();
                intArrays[currPos.y, currPos.x] = 2; // 방문처리

                for (int i = 0; i < 4; i++)
                {
                    // 범위를 벗어날 수 없으므로 예외처리하지 않음 (0,0 ~ 101,101)
                    Pos movePos = new Pos(currPos.y + dirY[i], currPos.x + dirX[i], currPos.count + 1);

                    // 목표 지점에 도착
                    if (movePos.y == itemY && movePos.x == itemX)
                    {
                        // 모든 좌표 * 2 였기 때문에 이동 횟수 / 2
                        answer = movePos.count / 2; 
                        queue.Clear();
                        break;
                    }

                    if (intArrays[movePos.y, movePos.x] == 1)
                        queue.Enqueue(movePos);
                }
            }

            return answer;
        }
    }