컴굥일지

[Programmers/프로그래머스 lv3][C++] 아이템 줍기 본문

알고리즘/코테 문제

[Programmers/프로그래머스 lv3][C++] 아이템 줍기

gyong 2023. 8. 17. 12:52
반응형

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87694 (문제가 길기 때문에, 전체 내용은 링크에서 확인) 

프로그래머스 아이템 줍기

 

문제 내용

직사각형이 여러 개 주어진다. 캐릭터는 이 직사각형들을 다 합쳤을 때의 나타나는 다각형의 테두리만을 걸어 다닐 수 있다.

캐릭터의 좌표와 아이템의 위치가 주어질 때, 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 출력하면 된다.

 

(아래는 주의 사항)

1. 직사각형이 다른 직사각형에 포함되는 경우는 없다.

2. 직사각형들이 서로 꼭짓점에서 만나거나, 변이 겹치는 경우는 없다.

3. 직사각형들을 다 합치면 반드시 하나의 다각형이 나온다.

4. 캐릭터,아이템의 위치는 반드시 다각형의 테두리에 위치한다.

 

문제 풀이

이 문제는 중간에 유연한 사고를 필요로 한다. (나는 못해서 구글링 해봤다..)

이 문제는 2가지 단계로 나누어진다.

1. 사각형들을 합쳐 다각형의 테두리 그리기 => 단순 구현

2. 캐릭터가 아이템까지 가는 거리 구하기 => bfs 사용

 

1. 사각형들을 합쳐 다각형의 테두리 그리기

arr 이차원 배열에 다각형을 그리려고 한다. 

다각형의 테두리만 true로, 외부/내부는 false로 표시하려면 2단계가 필요하다.

  1. 먼저 모든 사각형들의 테두리 라인만 true로 표시한다. => initArrWithRectangleLine()
  2. 이후 모든 사각형들의 "내부" 부분을 false로 표시한다.  => initArrWithRectangleBlank()

(주의: 1번이 다 끝나고 2번을 실행해야만 한다.)

void initArrWithRectangleLine(vector<int> &rectangle) {
    int lx = rectangle[0] * 2; // bfs에서 걸리지 않게 2배로 해서 넣음
    int ly = rectangle[1] * 2;
    int rx = rectangle[2] * 2;
    int ry = rectangle[3] * 2;

    for (int i = lx; i <= rx; i++) {
        arr[ly][i] = true;
        arr[ry][i] = true;
    }
    for (int i = ly; i <= ry; i++) {
        arr[i][lx] = true;
        arr[i][rx] = true;
    }
}

void initArrWithRectangleBlank(vector<int> &rectangle) {
    int lx = rectangle[0] * 2;
    int ly = rectangle[1] * 2;
    int rx = rectangle[2] * 2;
    int ry = rectangle[3] * 2;

    // 사각형의 내부는 전부 false 세팅
    for (int i = ly + 1; i < ry; i++) {
        for (int j = lx + 1; j < rx; j++) {
            arr[i][j] = false;
        }
    }
}

void initArrWithRectangles(vector<vector<int>> &rectangles) {
    for (auto rectangle : rectangles) // 사각형들 테두리 그리기
        initArrWithRectangleLine(rectangle);
    for (auto rectangle : rectangles) // 사각형들 내부의 테두리 지우기
        initArrWithRectangleBlank(rectangle);
}

 

2. 캐릭터가 아이템까지 가는 거리 구하기

여기서는 간단하게 BFS를 돌리면 된다. Y가 행이고, X가 열이라는 사실을 반드시 염두해둬야 한다.

queue<pair<int, int>> q;
    q.push({characterY, characterX});    // 주의!! Y가 행이다.
    visited[characterY][characterX] = 1; // 1로 시작하니 나중에 -1 해야 함

    while (!q.empty()) {
        auto point = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = point.first + dy[i];
            int nx = point.second + dx[i];

            if (arr[ny][nx] && visited[ny][nx] == 0) { // 테두리이고, 아직 방문하지 않았을 때
                q.push({ny, nx});
                visited[ny][nx] = visited[point.first][point.second] + 1;
            }
        }
    }

 

Q) 그럼 도대체 유연한 사고는 어디서 필요한 걸까?

위 코드를 바탕으로 문제를 풀면, 반드시 틀리는 항목이 나타난다.

그 이유는 아래와 같이 뭉치는 부분이 발생할 수 있기 때문이다.

프로그래머스 아이템 줍기

위와 같이 테두리가 붙어버리게 되면, bfs를 돌렸을 때 이동거리가 잘못 계산되게 된다.

 

위 문제를 해결하기 위해서 유연한 사고가 필요하다.

모든 것을 2배로 늘리면 된다! 

모든 좌표에 *2를 하면, 테두리가 뭉치지 않게 된다.

나중에 이동거리 출력 시에만 /2 해주면 되기 때문에, 좌표를 2배로 해서 계산하도록 하자.

 

아래는 전체 코드이다.

 

전체 코드

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

using namespace std;

//102로 여유있게 선언하여, bfs 탐색 시 좌표 범위 체크를 안 하도록 함
//어차피 테두리 아닌 부분과 마찬가지로 false 세팅 됨
//101로 세팅했다가, 101f라인에 테두리가 있으면 범위 체크가 필요하다.
bool arr[102][102];
int visited[102][102];

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

void initArrWithRectangleLine(vector<int>& rectangle){
    int lx=rectangle[0]*2; // bfs에서 걸리지 않게 2배로 해서 넣음
    int ly=rectangle[1]*2;
    int rx=rectangle[2]*2;
    int ry=rectangle[3]*2;
    
    for(int i=lx;i<=rx;i++){
        arr[ly][i]=true;
        arr[ry][i]=true;
    }
    for(int i=ly;i<=ry;i++){
        arr[i][lx]=true;
        arr[i][rx]=true;
    }
}

void initArrWithRectangleBlank(vector<int>& rectangle){
    int lx=rectangle[0]*2;
    int ly=rectangle[1]*2;
    int rx=rectangle[2]*2;
    int ry=rectangle[3]*2;
    
    //사각형의 내부는 전부 false 세팅
    for(int i=ly+1; i<ry;i++){
        for(int j=lx+1;j<rx;j++){
            arr[i][j]=false;
        }
    }
}

void initArrWithRectangles(vector<vector<int>>& rectangles){
    for(auto rectangle : rectangles) // 사각형들 테두리 그리기
        initArrWithRectangleLine(rectangle);
    for(auto rectangle : rectangles) // 사각형들 내부의 테두리 지우기
        initArrWithRectangleBlank(rectangle);
}

int solution(vector<vector<int>> rectangles, int characterX, int characterY, int itemX, int itemY) {
    initArrWithRectangles(rectangles);
    characterX*=2; characterY*=2; itemX*=2; itemY*=2;

    queue<pair<int,int>> q;
    q.push({characterY, characterX}); // 주의!! Y가 행이다.
    visited[characterY][characterX]=1; //1로 시작하니 나중에 -1 해야 함
    
    while(!q.empty()){
        auto point = q.front();
        q.pop();
        
        for(int i=0;i<4;i++){
            int ny = point.first + dy[i];
            int nx = point.second + dx[i];
            
            if(arr[ny][nx] && visited[ny][nx]==0){ //테두리이고, 아직 방문하지 않았을 때
                q.push({ny,nx});
                visited[ny][nx]=visited[point.first][point.second]+1;
            }
        }
    }
    
    return (visited[itemY][itemX]-1)/2;
    
}
반응형
Comments