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

해설

캐릭터 위치부터 아이템 위치까지 최단 거리를 구하는 bfs 문제이다.

캐릭터 위치를 출발지로 하여 테두리에 해당하는 좌표들로 이동한다. 

출발지로부터 각 좌표까지의 거리를 dist[x][y] 배열에 저장해 나가고, dist[아이템X][아이템Y]를 리턴하면 된다.

 

그럼, 테두리에 해당하는지 여부는 어떻게 표시할 수 있을까?

전체 직사각형의 영역을 먼저 표시한 후 사각형 내부만 다시 0으로 변경하면 된다.

 

//x: 세로좌표, y: 가로좌표로 처리

//직사각형 부분을 1로 채우기
for (int i=0; i<(int)rectangle.size(); i++) {

    int x1 = rectangle[i][1];
    int y1 = rectangle[i][0];
    int x2 = rectangle[i][3];
    int y2 = rectangle[i][2];

    for (int j=x1; j<=x2; j++) {
        for (int k = y1; k<=y2; k++) {
            board[j][k] = 1;
        }
    } 
}

//직사각형 내부만 0으로 채우기
//결국 board에는 직사각형 테두리만 남게 됨
for (int i=0; i<(int)rectangle.size(); i++) {

    int x1 = rectangle[i][1];
    int y1 = rectangle[i][0];
    int x2 = rectangle[i][3];
    int y2 = rectangle[i][2];

    for (int j=x1+1; j<x2; j++) {
        for (int k = y1+1; k<y2; k++) {
            board[j][k] = 0;
        }
    } 
}

 

 

그런데, 위와 같이 구현하면 이동방향이 명확히 표현되지 않는 경우가 발생한다.

예를 들어, 문제에서 제시한 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 의 테두리를 표시해보자.

하늘색으로 표시한 부분을 보면, 다닥다닥 1이 붙어 진행 방향이 명확히 표현되지 않는다. 

모든 직사각형의 크기 및 좌표를 2배로 만들어 위와 같은 문제를 처리하자.

 

기존 대비 2배 크기로 테두리를 셋팅한 후, bfs 로 아이템 좌표 (itx*2, ity*2)까지의 최단거리를 구하자.

dist[itx*2][ity*2]를 2로 나누어 리턴하면 정답이다.

 

 

전체 코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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

int chx, chy, ix, iy;
int board[110][110];
int dist[110][110];

void setDist() {
    
    for (int i=0; i<110; i++) {
        for (int j=0; j<110; j++)
            dist[i][j] = -1;
    }
}

void setBoard(const vector<vector<int>>& rectangle) {
    
    //직사각형 부분을 1로 채우기
    for (int i=0; i<(int)rectangle.size(); i++) {
        
        int x1 = rectangle[i][1]*2;
        int y1 = rectangle[i][0]*2;
        int x2 = rectangle[i][3]*2;
        int y2 = rectangle[i][2]*2;
        
        for (int j=x1; j<=x2; j++) {
            for (int k = y1; k<=y2; k++) {
                board[j][k] = 1;
            }
        } 
    }
    
    //직사각형 내부만 0으로 채우기
    //결국 board에는 직사각형 테두리만 남게 됨
    for (int i=0; i<(int)rectangle.size(); i++) {
        
        int x1 = rectangle[i][1]*2;
        int y1 = rectangle[i][0]*2;
        int x2 = rectangle[i][3]*2;
        int y2 = rectangle[i][2]*2;
        
        for (int j=x1+1; j<x2; j++) {
            for (int k = y1+1; k<y2; k++) {
                board[j][k] = 0;
            }
        } 
    }
}

bool OOB(int x,  int y) {
    return x < 0 || x >= 110 || y < 0 || y >= 110;
}

int bfs() {
    
    queue<ii> q;
    q.push({chx*2, chy*2});
    dist[chx*2][chy*2] = 0;
    
    while (!q.empty()) {
        
        ii cur = q.front();
        q.pop();
        
        if (cur.X == ix*2 && cur.Y == iy*2) return dist[cur.X][cur.Y]/2;
        
        for (int i=0; i<4; i++) {
            int nx = cur.X+dx[i];
            int ny = cur.Y+dy[i];
            if (OOB(nx, ny)) continue;
            if (!board[nx][ny] || dist[nx][ny] != -1) continue;
            q.push({nx, ny});
            dist[nx][ny] = dist[cur.X][cur.Y]+1;
        }
    }
    
    return -1;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    
    //x:세로좌표, y:가로좌표
    //모든 좌표를 2배씩 늘려 처리

    ix = itemY, iy = itemX;
    chx = characterY, chy = characterX;
    
    setDist();
    setBoard(rectangle);   
    return bfs();
}