프로그래머스 : 깊이/너비 우선 탐색(DFS/BFS) > 아이템 줍기(lv3)

프로그래머스 링크

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

프로그래머스

문제 설명

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.

즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.

다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

제한사항

• rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
• rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
  • 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
  • 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
  • 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
• charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• itemX, itemY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

---

• 전체 배점의 50%는 직사각형이 1개인 경우입니다.
• 전체 배점의 25%는 직사각형이 2개인 경우입니다.
• 전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.

---

입출력 예rectanglecharacterXcharacterYitemXitemYresult

[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]]	1	3	7	8	17
[[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]]	9	7	6	1	11
[[1,1,5,7]]	1	1	4	7	9
[[2,1,7,5],[6,4,10,10]]	3	1	7	10	15
[[2,2,5,5],[1,3,6,4],[3,1,4,6]]	1	4	6	3	10

문제 풀이

위의 그림과 같이 테두리를 만들어야 한다고 가정을 해보자

1. 모든 사각형을 저장할 수 있는 n x n 만큼의 Map배열을 만드는데 사각형들을 전부 *2만큼의 크기로 만들거기때문에

그 점 유의해주셔야 합니다(2배로 만드는 이유는 아래에 설명)

 

2. Map에 사각형을 저장을 해야하는데 필자의 경우

4 * 4의 사각형과 2* 2를 저장한다고 가정하면

테두리는 1 내부는 2의 값으로 저장을 해주었다.

그러면

0 1 1 0

1 2 2 1

1 2 2 1

1 2 2 1

1 1 1 1

과같은 모양이 Map배열에 저장이 된다.

12시 방향 2*2 사각형 한개 아래부분에 4*4 사각형 한개

겹치는부분, 내부부분은 2로 표현

 

3. 위와 같은 방식으로 모든 사각형들을 저장한뒤

Map을 돌면서 2인 값들을 전부 0 으로 바꿔준다

그러면 위의 우측사진처럼 테두리의 값만 1의 형태로 남게된다.

ex)

0 1 1 0

1 0 0 1

1 0 0 1

1 0 0 1

1 1 1 1

 

4. 그 상태에서 BFS형태로 반복을 돌렸는데 이때 주의해야할점이 있다.

위의 그림 (3, 5), (4, 5), (3, 6), (4, 6)지점을 보면 서로 1칸씩이라서

BFS알고리즘을 이용하여 위 문제를 풀이하려고 한다면 문제가 발생하게된다

(최종 결과값이 정답의 -1의 값으로 나오게된다)

 

5. 그래서 배열과 캐릭터위치, 아이템 위치를 전부 *2를 해준뒤 처리를 하면 정상적으로 처리가 된다

이때 마지막에 결과값은 / 2를 해주어야된다.

 

코드

필자는 매개변수 X,와 Y의를 바꿔서 풀이함

#include <string>
#include <vector>
#include <queue>

using namespace std;

int Map[102][102];
int Dist[102][102];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int solution(vector<vector<int>> rectangle, int characterY, int characterX, int itemY, int itemX) {
    int answer = 0;
    
    characterY *= 2;
    characterX *= 2;
    itemY *= 2;
    itemX *= 2;
    
    size_t RectangleSize = rectangle.size();
    
    // 사각형의 가장자리는 1로 내부는 2로 채운다
     for (size_t k = 0; k < RectangleSize; ++k)
    {
        for (int i = rectangle[k][1] * 2; i <= rectangle[k][3] * 2; ++i)
        {
            for (int j = rectangle[k][0] * 2; j <= rectangle[k][2] * 2; ++j)
            {
                if ((i > rectangle[k][1] * 2 && i < rectangle[k][3] * 2) &&
                    (j > rectangle[k][0] * 2 && j < rectangle[k][2] * 2))
                {
                    Map[i][j] = 2;
                }
                else
                {
                    if (Map[i][j] != 2)
                        Map[i][j] = 1;
                }
            }
        }
    }

    // 전부 채운다음 2인부분을 전부 0으로 바꿔준다.
    for (int i = 0; i < 102; ++i)
    {
        for (int j = 0; j < 102; ++j)
        {
            if (Map[i][j] == 2)
            {
                Map[i][j] = 0;
            }
        }
    }

    for (int i = 0; i < 102; ++i)
    {
        fill(Dist[i], Dist[i] + 102, -1);
    }

    // 그러면 가장자리만을 표시하게됨
    queue<pair<int, int>> qPair;

    qPair.push({ characterX, characterY });
    Dist[characterX][characterY] = 0;

    while (!qPair.empty())
    {
        pair<int, int> Cur = qPair.front();
        qPair.pop();

        for (int Dir = 0; Dir < 4; ++Dir)
        {
            int NextX = Cur.first + dx[Dir];
            int NextY = Cur.second + dy[Dir];

            if (NextX < 0 || NextY < 0 || NextX >= 102 || NextY >= 102)
                continue;
            if (Dist[NextX][NextY] != -1 || Map[NextX][NextY] != 1)
                continue;

            Dist[NextX][NextY] = Dist[Cur.first][Cur.second] + 1;
            qPair.push({ NextX, NextY });
        }
    }

    answer = Dist[itemX][itemY] / 2;
    
    return answer;
}

정확성