해설
캐릭터 위치부터 아이템 위치까지 최단 거리를 구하는 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();
}
'ㄴ 알고리즘 > 프로그래머스풀이' 카테고리의 다른 글
[프로그래머스 lv3] 선입 선출 스케줄링 풀이 (0) | 2022.09.22 |
---|---|
[프로그래머스 lv3] 매칭 점수 풀이 (0) | 2022.09.20 |
[프로그래머스 lv3] 모두 0으로 만들기 풀이 (0) | 2022.09.20 |
[프로그래머스 lv3] 블록 이동하기 풀이 (0) | 2022.09.19 |
[프로그래머스 lv3] 광고 삽입 풀이 (0) | 2022.09.19 |
댓글