프로그래머스 / level.3 / 아이템 줍기(C++)

내 풀이

• 주어진 사각형들의 내부에 포함되지 않은 외곽선을 따라 DFS 탐색을 하여 문제를 풀었다.
• 하지만 ‘사각형 내부에 포함되지 않은 외곽선’ 이라는 조건에 따라 1씩 이동하며 외곽선을 탐색하면 아래와 같은 영역에서 문제가 생긴다.

• 바로 간격이 1이면서 외곽선으로 연결되지 않은 영역이다.
• 이 영역은 외곽선으로 연결되지 않았지만, 현재 위치와 간격이 1이면서 사각형 내부에 포함되지 않은 외곽선이므로 내가 설정한 조건에 참이 된다.
• 이것을 방지하기 위해 좌표값을 2배로 한 뒤 1씩 탐색하였다. 이렇게 하면 원본에서 외곽선으로 이어지지 않은 좌표를 구별해낼 수 있다.

내 해답

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    vector<int> counters;
    stack<pair<int, int>>  s;
    vector<vector<bool>>   visit(101, vector<bool>(101, false));
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    
    // 시작점 입력 (좌표 2배)
    s.push(make_pair(characterX * 2, characterY * 2));
    
    int count = -1;
    while(!s.empty())
    {
        int X = s.top().first;
        int Y = s.top().second;
        s.pop();
        
        // 이미 방문한적 있으면 탐색 x
        if(visit[X][Y])
            continue;
        
        // 방문 횟수 증가
        ++count;
        
        // 목표지점(좌표 2배)이라면 카운트 목록에 추가
        if(X == itemX * 2 && Y == itemY * 2)
        {
            counters.push_back(count);
            count = 0;
            continue;
        }
        
        // 목표지점이 아니라면 방문 체크
        visit[X][Y] = true;

        
        // 다음 위치 찾기
        for(int i = 0; i < 4; ++i)
        {
            int nX = X + dx[i];
            int nY = Y + dy[i];
            
            // 범위 밖일 경우
            if(nX < 0 || nX > 100 || nY < 0 || nY > 100)
                continue;
            
            if(!visit[nX][nY])
            {
                bool isOutline = false;
                
                for(const auto& r : rectangle)
                {
                    // 사각형 좌표 2배
                    int lbX = r[0] * 2;
                    int rtX = r[2] * 2;
                    int lbY = r[1] * 2;
                    int rtY = r[3] * 2;
                    
                    // 한 점이라도 사각형 내부라면 외각선이 아니다
                    if(nX > lbX && nY > lbY && nX < rtX && nY < rtY)
                    {
                        isOutline = false;
                        break;
                    }
                    
                    // 외곽선 테스트
                    // x축
                    if(nX == lbX || nX == rtX)
                    {
                        if(nY >= lbY && nY <= rtY)
                        {
                            isOutline = true;
                            continue;
                        }
                    }
                    // y축
                    if(nY == lbY || nY == rtY)
                    {
                        if(nX >= lbX && nX <= rtX)
                        {
                            isOutline = true;
                            continue;
                        }
                    }
                }
                
                // 아웃라인 위에 있을 경우
                if(isOutline)
                {
                    s.push(make_pair(nX, nY));
                }
            }
        }
    }
    
    answer = *min_element(counters.begin(), counters.end());
    answer /= 2;
    
    return answer;
}