프로그래머스 [Level3] 아이템 줍기

 

 

 

#include <string>
#include <vector>
#include <deque>

using namespace std;


int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    
    int answer = 0;
    vector<vector<int>> m_vecArray(102, vector<int>(101, -1));
    vector<vector<int>> m_vecVisit(102, vector<int>(101, -1));

    // 방문가능한곳 설정하기 
    for (auto& iter : rectangle)
    {
        int start_x, start_y = 0;
        int end_x, end_y = 0;

        start_x = iter[0]*2;
        start_y = iter[1]*2;

        end_x = iter[2]*2;
        end_y = iter[3]*2;

        // 여기서 방문가능한곳만 1로 표시 

        for (int i = 0; i <= end_y-start_y; i++)
        {
            if(m_vecArray[start_x][start_y + i] !=2)
                m_vecArray[start_x][start_y+i] = 1; // 첫  세로

            if (m_vecArray[end_x][start_y + i] != 2)
                m_vecArray[end_x][start_y+i]= 1;  // 마무리 세로 
         }

        for (int j = 0; j <= end_x-start_x; j++)
        {
            if(m_vecArray[start_x + j][start_y] !=2)
                 m_vecArray[start_x + j][start_y] = 1; // 첫 가로  

            if(m_vecArray[start_x + j][end_y] !=2)
                 m_vecArray[start_x + j][end_y]= 1;  // 위 가로 
        }

        // 즉 안쪽은 다 없애야함 
        for (int i = start_x; i < end_x; i++)
        {
            for (int j = start_y; j < end_y; j++)
            {
                if (i > start_x && i < end_x )
                {
                    if (j > start_y && j < end_y)
                    {
                        m_vecArray[i][j] = 2;
                    }
                }
            }
        }
    }


    deque<pair<int, int>> m_dequeCurPos;


    m_dequeCurPos.push_back(make_pair(characterX*2, characterY*2));
    m_vecVisit[characterX*2][characterY*2] = 0;

    while (!m_dequeCurPos.empty())
    {
        int i_CurX = m_dequeCurPos.front().first;
        int i_CurY = m_dequeCurPos.front().second;

        m_dequeCurPos.pop_front();

        // 탈출 조건 
        if (i_CurX == itemX*2 && i_CurY == itemY*2)
        {
            answer = m_vecVisit[i_CurX][i_CurY]/2;
            break;
        }


        // 범위 설정 

        //동
        if (i_CurX + 1 >= 0 && i_CurY >= 0)
        {
            if (m_vecArray[i_CurX + 1][i_CurY] == 1 && m_vecVisit[i_CurX + 1][i_CurY] == -1) // 갈 수 있는 경로면서 한번도 안지나온 곳
            {
                m_vecVisit[i_CurX + 1][i_CurY] = m_vecVisit[i_CurX][i_CurY] + 1; // 방문기록 및 온 경로 횟수 저장
                m_dequeCurPos.push_back(make_pair(i_CurX + 1, i_CurY));
            }
        } 

        // 서 (4,6에서 3,6으로 갈때 문제발생) -> 3,6을 어디선가 이미 방문 
        if (i_CurX - 1 >= 0 && i_CurY >= 0)
        {
            if (m_vecArray[i_CurX - 1][i_CurY] == 1 && m_vecVisit[i_CurX - 1][i_CurY] == -1) //  갈 수 있는 경로면서 한번도 안지나온 곳
            {
                m_vecVisit[i_CurX - 1][i_CurY] = m_vecVisit[i_CurX][i_CurY] + 1; // 방문기록 및 온 경로 횟수 저장
                m_dequeCurPos.push_back(make_pair(i_CurX - 1, i_CurY));
            }
        }


        // 남
        if (i_CurX >= 0 && i_CurY - 1 >= 0)
        {
            if (m_vecArray[i_CurX][i_CurY - 1] == 1 && m_vecVisit[i_CurX][i_CurY - 1] == -1) // 갈 수 있는 경로면서 한번도 안지나온 곳
            {
                m_vecVisit[i_CurX][i_CurY - 1] = m_vecVisit[i_CurX][i_CurY] + 1; // 방문기록 및 온 경로 횟수 저장
                m_dequeCurPos.push_back(make_pair(i_CurX, i_CurY - 1));
            }
        }


        // 북
        if (i_CurX >= 0 && i_CurY + 1 >= 0)
        {
            if (m_vecArray[i_CurX][i_CurY + 1] == 1 && m_vecVisit[i_CurX][i_CurY + 1] == -1) //  갈 수 있는 경로면서 한번도 안지나온 곳
            {
                m_vecVisit[i_CurX][i_CurY + 1] = m_vecVisit[i_CurX][i_CurY] + 1; // 방문기록 및 온 경로 횟수 저장
                m_dequeCurPos.push_back(make_pair(i_CurX, i_CurY + 1));
            }
        }

 	}

    

    
    
    return answer;
}

 

 

문제 접근 순서 

 

1. 이 문제는 최단 경로를 찾는 문제임을 파악하고 바로 BFS 알고리즘을 생각 

 

2. 다음으로 갈 수 있는 영역과 갈 수 없는 영역을 나누어 생각하려고함 

    따라서 좌표공간처럼 생각하여 문제를 풀기로함.

   (연습장에 직접 직사각형을 그려보고 좌표 범위를 생각해보면 쉽게 규칙성을 찾을 수 있다.) 

   (한가지 더 생각할게 직사각형 안은 제외 해야하므로 따로 "2"로 표시하여 해당 길을 다시 갈 수 있는 길로 갱신하지 못하도록 하      였다.) 

 

3. 예시 그림을 보면 간격이 1인 구간의 직사각형 구간이 있어 Jump 할 수 있는 상황이 나옴 

참고

   다음과 같이 빨간색 동그라미 부분에서 오류가 발생한다 그냥 동서남북으로 진행할 시에는. 

   따라서 저런 경우를 배제해주기 위해 좌표 공간을 2배 확대하여 계산한다. 

  그러면 거리가2가 되므로 점프할 수 없게 된다. 

 

 4. 좌표공간을 2배 해줬으므로 답 또한 나누기2를 해야할 것을 생각함.