[C++] 아이템 줍기

[문제]

코딩테스트 연습 - 아이템 줍기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

bfs를 이용한 문제인데 몇가지 주의사항을 알아야 답이 도출되는 문제이다.

우선은 문제를 풀기 위해서 3가지 과정을 걸쳐서 답이 나오게 만들었다.

 

1. 직사각형의 테두리 칠하기.

2. 직사각형 테두리 내부 0으로 초기화하기

3. bfs를 이용해서 직사각형의 테두리 둘레를 따라서 돌아다니기.

 

*주의사항 : 2번의 테두리 내부를 0으로 초기화 하는 과정은 테두리를 모두 칠한뒤에 해야 한다. 테두리를 칠하면서 동시에 0으로 바꾸면 내부에 선이 남아있는 문제가 발생할 수 있다.

 

이렇게 1 -> 2 -> 3번의 과정을 걸치면 답이 쉽게 나올 수 있는데 주의사항이 1개가 더 남아 있다.

 

위의 표에서 왼쪽은 좌표를 바꾸지 않고 만든 결과이고 오른쪽은 좌표의 모든 값을 2배로 올린뒤에 만든 결과이다.

그림으로 보면 알 수 있듯이 평범하게 접근을 하면 1의 숫자가 겹치는 부분이 생기기에 모든 좌표를 n배수로(나의 경우는 2배수를 하였다.) 올린 뒤에 마지막 계산에서 길이값을 n으로 나눠서 답을 내야 한다.

[코드]

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

using namespace std;

int polygon[106][106];
int visited[106][106];

int bfs(int charX, int charY, int itemX, int itemY){
    queue<pair<pair< int ,int >, int> > line;
    line.push(make_pair(make_pair(charY,charX),0));
    
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    
    while(line.size() > 0){
        int curX = line.front().first.second;
        int curY = line.front().first.first;
        int curS = line.front().second;
        line.pop();
        if(curX == itemX && curY == itemY){
            return curS;
        }
        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(polygon[nextY][nextX] == 1){
                if(visited[nextY][nextX] == 0){
                    visited[nextY][nextX] = 1;
                    line.push(make_pair(make_pair(nextY,nextX), curS + 1));
                }
            }
        }
    }
    
    return 0;
}

void rectangle_zero(vector<vector<int> > rectangle){
    
    for(int i = 0;i<rectangle.size();i++){
        int leftX = rectangle[i][0] * 2;
        int leftY = rectangle[i][1] * 2;
        int rightX = rectangle[i][2] * 2;
        int rightY = rectangle[i][3] * 2;

        for(int j = leftX + 1; j < rightX; j++){
            for(int k = leftY + 1; k < rightY; k++){
                polygon[k][j] = 0;
            }
        }
    }
    
    return;
}

void rectangle_one(vector<vector<int>> rectangle){
    
    for(int i = 0;i<rectangle.size();i++){
        //좌측 하단 좌표부터 우측 상단 좌표까지 네모 테두리를 1로 바꿔주자.
        int leftX = rectangle[i][0] * 2;
        int leftY = rectangle[i][1] * 2;
        int rightX = rectangle[i][2] * 2;
        int rightY = rectangle[i][3] * 2;
        
        polygon[leftY][leftX] = 1;
        polygon[rightY][rightX] = 1;
        
        for(int j = leftY; j <= rightY; j++){
            polygon[j][leftX] = 1;
        }
        
        for(int j = leftX; j <= rightX; j++){
            polygon[leftY][j] = 1;
        }
        
        for(int j = leftX; j <= rightX; j++){
            polygon[rightY][j] = 1;
        }
        
        for(int j = leftY; j <= rightY;j++){
            polygon[j][rightX] = 1;
        }
    }

    
    return;
}

void look_polygon(){
    
    for(int i = 30;i >= 0;i--){
        for(int j = 0;j <= 30;j++){
            if(polygon[i][j] == 0){
                cout<<"  ";
            }
            else{
                cout<<polygon[i][j]<<" ";
            }
        }
        cout<<endl;
    }
    
    return;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    
    //직사각형들 테두리 칠하기.
    rectangle_one(rectangle);
    
    //직사각형들 테두리 내부를 0으로 만들기.
    rectangle_zero(rectangle);
    
    // look_polygon();    
    
    //bfs를 이용해서 1인 좌표들을 순서대로 가기.
    answer = bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2) / 2;
    
    return answer;
}