문제 정의
- 다각형 모양의 지형과 현재 캐릭터의 위치, 아이템이 놓인 위치가 주어진다.
- 다각형 모양의 지형은 사각형 배열 rectangle에 의해 주어지고, 여러 사각형이 겹쳐져있는 형태로 구성돼있다.
- 캐릭터는 겹쳐진 사각형들의 가장자리로만 이동을 할 수 있고, 현재 캐릭터의 위치나 아이템의 위치 또한 이 가장자리 경로상에 놓여있다.
- 캐릭터는 한 턴에 한 칸씩 이동할 때, 현재 위치에서 아이템이 놓인 위치로 가장 짧은 경로로 이동할 때의 이동거리를 리턴
- 제약사항은 다음과 같다.
- 모든 사각형이 겹쳐진 최종 지형은 무조건 하나의 덩어리이다.
- rectangle 사각형들 중에서, 임의의 사각형이 다른 사각형을 포개는 형태는 없다.
- 모서리를 서로 공유하는 사각형은 주어지지 않는다.
- 지형의 중간에 빈 공간이 생긴다고 해도, 무조건 최외각 경로로만 이동할 수 있다.
문제 해결 접근
최외각 경로 설정
- 이 문제의 관건은 최외각 경로를 설정하는 것이다.
- 최외각 경로를 설정하는 것은 rectangle의 모든 사각형 배열을 순회하면서, 이중 for문을 통해, 현재 사각형의 외각라인이라면 2로 표시하고, 내부 영역이라면 1이라고 표시한다.
- 표시하려는 위치에 이미 1로 표시되어있다면, 이미 지형의 내부라는 뜻이기 때문에 넘어간다.
- 2차원 int 배열 map을 선언해서, 최외각 경로를 설정해놓은 다음에, bfs로 해당 경로를 이동하면서 가장 먼저 item의 위치에 도착할 때의 이동 수를 리턴하면 된다.
예외 발생 문제
- 문제는, 이동을 무조건 좌표상에서 1칸씩 하기 때문에, 다음과 같은 상황에서 예외가 발생한다.
- 정석 경로는 굵은 검은색 테두리이지만, 코드상으로는 빨간색 경로도 정상 경로로 인식해버린다.
- 파란색 좌표 지점에서 경로를 탐색할 때, 다음 위치를 찾기 위해서 dir배열을 이용할 것이다.
- 캐릭터의 이동은 현재 위치에서 상하좌우 한 칸씩 이동할 수 있기 때문에, 파란색 위치에서, 한칸 위에 있는 검은색 경로로 바로 뛰어넘어 버릴 수 있게 된다.
- 이를 방지하기 위해서, 애초에 map의 크기를 기존의 크기에 2배로 하여 설정한다.
- 이렇게 되면 지형 전체가 2배가 되고, 한 칸씩 이동한다고 해도, 위와 같은 예외가 발생하지 않게 된다. 이제 한 칸 위에는 아무 것도 없다.
코드
import java.util.*;
class Solution {
int[][] map = new int[101][101];
int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
boolean [][] visit = new boolean[101][101];
class Game{
int curX;
int curY;
int cnt;
public Game(int curX, int curY, int cnt){
this.curX = curX;
this.curY = curY;
this.cnt = cnt;
}
}
Queue<Game> queue = new LinkedList<>();
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
for(int[] rect : rectangle){
int xStart = 2*rect[0];
int yStart = 2*rect[1];
int xEnd = 2*rect[2];
int yEnd = 2*rect[3];
for(int i = yStart; i<=yEnd;i++){
for(int j = xStart; j<=xEnd;j++){
if(map[i][j]==1)
continue;
if(i==yStart||i==yEnd||j==xStart||j==xEnd){
map[i][j] = 2;
continue;
}
map[i][j] = 1;
}
}
}
queue.offer(new Game(2*characterX,2*characterY,0));
visit[2*characterY][2*characterX] = true;
return bfs(2*itemX, 2*itemY);
}
public int bfs(int itemX, int itemY){
while(!queue.isEmpty()){
Game game = queue.poll();
if(game.curX==itemX&&game.curY==itemY)
return game.cnt/2;
for(int i = 0 ;i<4;i++){
int newX = game.curX + dir[i][0];
int newY = game.curY + dir[i][1];
if(newX<0||newX>100||newY<0||newY>100)
continue;
if(map[newY][newX]==2&&!visit[newY][newX]){
visit[newY][newX] = true;
queue.offer(new Game(newX,newY,game.cnt+1));
}
}
}
return 0;
}
}느낀점
이 문제를 풀면서 고비는, 2차원 배열을 2배로 키우는 것이었다.
지형도 한 칸 단위이고, 이동도 한 칸 단위이기 때문에 발생하는 예외를 고려하지 못해서 시간이 오래 걸렸다.
최외각위치를 표시하는 알고리즘 구현도 생각보다 오래 걸렸다.
그리고 그림의 좌표와 실제 행렬의 좌표 구성이 아예 반대이기 때문에, 더 헷갈렸던 것 같다.
내부와 외부를 처리하는 방법을 이번 문제를 통해 제대로 알게된 것 같다.
영역 문제가 나오면 이런 식으로 풀면 될 것 같다.