https://school.programmers.co.kr/learn/courses/30/lessons/87694
문제
> 다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.
> 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.
> 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.
> 단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.
> 즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.
> 다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.
> 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.
> 지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때,
캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.
접근
일단 모든 직사각형의 정보에 대해서 해당 직사각형이차지하고 있는 좌표에 대해 표시를 한다.
테두리에 해당하는 부분은 1로 바꿔주고 아닌 부분은 방문처리만해준다.
이 때, 다른 직사각형들의 정보가 들어 올 때, 앞선 방문처리 했던 곳에 겹치게 된다면 테두리인지 확인하고 테두리가 아닌 부분은 싹 지워준다.
하지만 여기서 예제 1을 보면 계단식으로 꺾이는 부분이 있다. 이는 좌표상에서 처리하면 계단 부분이 인접하게 표시되므로 모든 좌표를 2배해서 늘려서 기록한다.
이제 테두리 부분만 1로 표시가 되고 계단부분도 잘 표시가 되어있다.
이제 주어진 시작점에서 아이템까지의 BFS를 탐색하며 최단거리를 구하고 2로 나눠주면 된다.
문제해결
> 좌표를 표현할 이차원 area배열을 선언하고 테두리를 찾기위한 boolean형 배열 visit와 뒤에서 BFS에 사용할 visited배열을 선언한다.
> 사방탐색을 위해 dir과 dic로 방향을 정의해준다.
> 먼저 모든 좌표를 2배로 늘려야하므로 1~50까지의 범위 51크기 + 0좌표까지해서 52 좌표의 두배로 104만큼 모든 크기를 준다.
> 주어진 사각형의 정보를 모두 돌며 현재 사각형의 대해 좌하단의 x,y를 x1과 y1으로 , 우상단의 x,y를 x2와 y2로 지정하고 이를 2배씩 해준다.
> 이제 해당 범위를 돌며 area 배열에 테두리 부분만 1로 마킹을하며 방문처리해준다.
> 만약 여기서 방문처리된 좌표가 다른 사각형에서 또 접근될 때, 해당 좌표가 현 사각형의 테두리에 해당 하지 않는다면 다시 0으로 바꿔 지워준다.
> 마킹이 끝나면 BFS에 시작좌표, 끝좌표를 전부 2배 해서 매개변수로 전달해 호출한다.
> 큐로 시작 좌표부터 시작해서 사방탐색을 하며 새로운 좌표를 찾는다.
> 새로운 좌표가 미방문좌표고 1로 표시된 테두리일 때, 큐에 해당 좌표를 넣고 이동거리 +1 해준뒤 방문처리해준다.
> 위 과정을 반복하며 탐색하는데 현 좌표가 아이템의 좌표면 탐색을 멈추고 현재까지의 이동 거리 /2를 반환한다.코드
import java.util.*;
import java.lang.*;
class Solution {
static int[][] area;
static boolean[][] visit, visited;
static int[] dir = {-1, 1, 0, 0};
static int[] dic = {0, 0, -1, 1};
static int answer = 0;
static void BFS(int sr, int sc, int er, int ec) {
Queue<Integer[]> q = new ArrayDeque<>();
q.add(new Integer[]{sr, sc, 0});
while(!q.isEmpty()) {
Integer[] cur = q.poll();
int y = cur[0];
int x = cur[1];
if(y == er && x == ec) {
answer = cur[2] / 2;
return;
}
for(int i = 0; i < 4; i++) {
int ny = y + dir[i];
int nx = x + dic[i];
if(visited[ny][nx] || area[ny][nx] != 1) continue;
q.add(new Integer[]{ny, nx, cur[2] + 1});
visited[ny][nx] = true;
}
}
}
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
area = new int[104][104];
visit = new boolean[104][104];
visited = new boolean[104][104];
for(int r = 0; r < rectangle.length; r++) {
int[] cur = rectangle[r];
int y1 = cur[1] * 2;
int y2 = cur[3] * 2;
int x1 = cur[0] * 2;
int x2 = cur[2] * 2;
for (int i = y1; i <= y2; i++) {
for(int j = x1; j <= x2; j++) {
if(visit[i][j]) {
if(i != y1 && i != y2 && j != x1 && j != x2)
area[i][j] = 0;
continue;
}
if(i == y1 || i == y2 || j == x1 || j == x2) {
if(!visit[i][j]) area[i][j] = 1;
}
visit[i][j] = true;
}
}
}
BFS(characterY * 2, characterX * 2, itemY * 2, itemX * 2);
return answer;
}
}후기
2배해줄 생각을 못하고 테두리 그린 뒤 꺾이는 지역에 대해 주변에 0이 2개미만인것으로 판정했는데 이때, 테스트케이스 2에서 완전히 막혔다.
방법을 고민하다가 그냥 2배 늘려서 보면 계단도 잘 표현될것 같아서 늘린다음 나누고자 했는데 잘 됐다.
