c++ 프로그래머스_"아이템 줍기"

https://programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

​

좌표 평면을 board라고 가정하고 진행한다.

​

rectangle의 사각형의 가장자리를 모두

board[y][x] = 1 로 지정했다.

즉, 이동할 수 있는 경로이다.

​

그리고 recatangle 사각형 내부를

이동할 수 없으니까

board[y][x] = 0으로 지정했다.

​

근데 그냥 이렇게

최대 크기 50으로 잡고

1칸씩 진행으로 하면

저 부분은

1 1 1

0 0 1

0 1 1

이런 식으로 표현되어

져 부분이 꺾여야되는데

​

간격 1칸인 board로 진행되면

1 1 1

0 1 1

이렇게 붙어져서 잘못된 이동경로를 가진다.

​

그래서 모든 좌표는 정수이므로 1칸 차이나는 것도 분리 시키기 위해

모든 좌표를 2배해줬다.

​

그럼 2의 배수만 이동 경로가 되므로

칸을 구별할 수 있다.

​

마지막 반환 값도 2배 해줬으니

/2 해줘서 반환한다.

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

typedef struct{
    int y,x;
    int cnt;
}node;

int board[101][101]; // 좌표 [y , x]
bool visit[101][101];

pair<int,int> dir[] = {{-1,0},{0,1},{1,0},{0,-1}};

bool is_in(int y, int x){
    if(x < 1 || y< 1 || x > 100 || y > 100 || board[y][x] == 0)
        return false;
    return true;
}

int bfs(int ch_x,int ch_y,int itemX,int itemY){

    queue<node> q;
    q.push({ch_y,ch_x,0});
    visit[ch_y][ch_x] = true;
    
    while(!q.empty()){
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
        if(x == itemX && y == itemY){
            return cnt/2;
        }
        
        for(int i=0;i<4;i++){
            int dy = dir[i].first;
            int dx = dir[i].second;
            
            if(is_in(y+dy, x+dx) && !visit[y+dy][x+dx]){
                visit[y+dy][x+dx] = true;
                q.push({y+dy,x+dx,cnt+1});
            }
            
        }
    }
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    
    for(int i=0;i<rectangle.size();i++){
        int left_x = rectangle[i][0]* 2, left_y = rectangle[i][1]* 2;
        int right_x = rectangle[i][2] * 2, right_y = rectangle[i][3]* 2;
        
        for(int i= left_x;i <= right_x ; i++){
            board[left_y][i] = 1;
            board[right_y][i] = 1;
        }
        
        for(int i= left_y;i <= right_y ; i++){
            board[i][left_x] = 1;
            board[i][right_x] = 1;
        }
    }
    
    for(int i=0;i<rectangle.size();i++){
        int left_x = rectangle[i][0]* 2, left_y = rectangle[i][1]* 2;
        int right_x = rectangle[i][2]* 2, right_y = rectangle[i][3]* 2;
     
        for(int i=left_y+1 ;i <= right_y -1 ;i++){
            for(int j = left_x+1 ; j<=right_x -1 ;j++){
                board[i][j] = 0;
            }
        }
    }
    
    answer = bfs(characterX* 2,characterY* 2,itemX*2,itemY*2);
    
    return answer;
}