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

문제 링크

아이템 줍기

 

풀이

BFS문제인데, 좌표를 두 배 확대하는 아이디어로 풀 수 있는 문제
2배하게 되면 각 영역의 점과 점을 잇는 선을 따로 구할 수 있어 겹치는 문제를 해결할 수 있다.

1. 각 좌표는 50이하로 들어오므로 배열은 원래 51 사이즈로 만들어야하는데, 두 배이기 때문에 102 크기로 만든다.
2. 사각형을 돌면서 각 좌표는 두 배해주고 1로 영역을 만들어준다.
3. 좌표의 시작+1부터 끝-1까지는 안쪽이기 때문에 0으로 만든다.
4. 외곽선을 BFS로 탐색하면서 거리를 구해주고, 답은 /2해줘야 나온다.

 

코드

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

using namespace std;

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

int bfs(int cx, int cy, int ix, int iy, vector<vector<int>> &outline)
{
    vector<vector<int>> dist(102, vector<int>(102, -1));
    queue<pair<int,int>> q;
    q.push({cy, cx});
    dist[cy][cx] = 0;

    while(!q.empty())
    {
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int ny = ty+dy[i];
            int nx = tx+dx[i];
            if(ny<0 || ny>102 || nx<0 || nx>102) continue;
            if(outline[ny][nx] == 0) continue;
            if(dist[ny][nx] != -1) continue;
            dist[ny][nx] = dist[ty][tx] + 1;
            q.push({ny,nx});
        }
    }

    return dist[iy][ix];
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;

    vector<vector<int>> arr(102, vector<int>(102));
    for(int i=0;i<rectangle.size();i++) // 영역 만들기
    {
        int sx = rectangle[i][0]*2;
        int sy = rectangle[i][1]*2;
        int ex = rectangle[i][2]*2;
        int ey = rectangle[i][3]*2;
        for(int j=sy;j<=ey;j++)
        {
            for(int k=sx;k<=ex;k++)
            {
                arr[j][k] = 1;
            }
        }
    }

    for(int i=0;i<rectangle.size();i++) // 외곽선 만들기
    {
        int sx = rectangle[i][0]*2;
        int sy = rectangle[i][1]*2;
        int ex = rectangle[i][2]*2;
        int ey = rectangle[i][3]*2;
        for(int j=sy+1;j<ey;j++)
        {
            for(int k=sx+1;k<ex;k++)
            {
                arr[j][k] = 0;
            }
        }
    }

    answer = bfs(characterX*2, characterY*2, itemX*2, itemY*2, arr) / 2;

    return answer;
}