[알고리즘/프로그래머스] 아이템 줍기 (Lv.3)

[ 문제이해 ]

 

이 문제는 좌표평면에 여러개의 사각형이 놓여 하나의 다각형의 형태로 이루어져 있을 때, 다각형의 둘레를 따라 캐릭터가 이동하며 아이템이 놓여있는 곳까지의 최소 거리를 구하는 문제이다.

문제의 경우에서는 2개 이상의 다각형 또는 한 직사각형이 다른 직사각형을 완전히 포함하는 경우를 제외하기 때문에 어렵지 않은 문제였다.

 

[ 문제풀이 ]

이 문제에서의 키 포인트라면 좌표 평면을 기준으로 플레이어가 둘레를 따라 움직여야 한다.

하지만 일반적인 DFS로 해결하려 한다면 위의 빨간줄을 따라 캐릭터가 이동한다면 캐릭터가 (3, 5)에 위치한다면 (4, 6)으로 이동할 뿐 아니라 (3, 6)으로도 이동할 수 있다.

이 방법은 생각보다 매우 쉽게 해결되었다.

그 방법은 바로 모든 좌표를 2배로 늘려주어 위의 그림과 같이 캐릭터가 이동할 수 없게 만들면 된다.(물론 답을 구할 때, 구한 답의 반을 해줘야 해결된다.)

 

위의 문제풀이를 이용하여 문제를 해결하면 된다.

[DFS]

나의 경우에는 중복적인 움직임을 제거하기 위해 visited 배열을 두었다.

이 visited 배열은 총 2가지의 형태로 구분하여 판단하였다.

1. 이미 방문하였거나 방문할 수 없는 구역(다각형의 안쪽 부분과 다각형의 둘레가 아닌 부분) : 0
2. 방문할 수 있는 구역(다각형의 둘레 부분, 캐릭터가 움직이는 구역) : 1

 

[ 전체 코드 ]

#include <string>
#include <vector>

using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int visited[101][101];
int answer = 2e9;

void dfs(int curX, int curY, int itemX, int itemY, int cnt)
{
    if(curX == itemX && curY == itemY)
    {
        answer = min(cnt, answer);
        return;
    }
    
    for(int i=0; i<4; i++)
    {
        int nx = curX + dx[i];
        int ny = curY + dy[i];
        
        if(visited[nx][ny] )
        {
            visited[nx][ny] = 0;
            dfs(nx, ny, itemX, itemY, cnt + 1);
            visited[nx][ny] = 1;
        }
    }
}
int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;
    
    for(int i=0; i<rectangle.size(); i++)
    {
        for(int x = rectangle[i][0] *2; x <=rectangle[i][2] * 2;x++)
        {
            for(int y = rectangle[i][1] * 2; y<= rectangle[i][3] * 2; y++)
            {
                visited[x][y] = 1;
            }
        }
    }
    
    for(int i=0; i<rectangle.size(); i++)
    {
        for(int x = rectangle[i][0] * 2 + 1; x <= rectangle[i][2] * 2 - 1; x++)
        {
            for(int y = rectangle[i][1] * 2 + 1; y<= rectangle[i][3] * 2 - 1; y++)
            {
                visited[x][y] = 0;
            }
        }
    }
    
    visited[characterX][characterY] = 1;
    dfs(characterX, characterY, itemX, itemY, 0);
        
    
    return answer / 2;
}