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

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.

즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.

다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

제한사항
rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
itemX, itemY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.
전체 배점의 50%는 직사각형이 1개인 경우입니다.
전체 배점의 25%는 직사각형이 2개인 경우입니다.
전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.

입출력 예

입출력 예 설명

입출력 예 #1

캐릭터 위치는 (1, 3)이며, 아이템 위치는 (7, 8)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

입출력 예 #2

캐릭터 위치는 (9, 7)이며, 아이템 위치는 (6, 1)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

입출력 예 #3

캐릭터 위치는 (1, 1)이며, 아이템 위치는 (4, 7)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

입출력 예 #4, #5

설명 생략

전략

1. 사각형의 각 꼭지점 좌표가 주어져있다.
2. 시작 지점 기준으로 사각형이 겹쳐지는 부분이 있는지 없는지 판단한다.
3. 겹쳐지는 부분이 있으면 길이 막혔다는 의미이다.
4. 막다른 곳에서는 위로, 혹은 아래로 올라간다.
5. 초반에 출발할 때 상, 하, 좌, 우 어디로 가야하는지 처음엔 모른다.
6. 그래서 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] 이렇게 상하좌우 모든 케이스를 따지고 최종적으로 움직여야하는 길이를 비교해야할 것 같다.
7. 처음 출발할 때는 보면 출발할 수 있는 경우의 수가 2가지 밖에 없다. 즉 한칸 움직였을 때 각 사각형 y 좌표의 범위를 벗어나면 그 방향으로는 갈 필요가 없다.
8. 내부까지 경로가 있는 미로 같은 형태가 아니라, 외부 라인만 따라가면 된다. 근데 내부인지, 아닌지 어떻게 판단해야하지 ? 주어진 정보는 사각형의 꼭지점이다.
9. 사각형의 좌표, 그리고 x,y 좌표를 받는 메소드를 만들어서 지금 내부에 해당하는지 안하는지 boolean 값을 리턴하는 메소드를 만들면 해결할 수 있을까?
10. 내가 현재 어떤 블록에 위치하고 있는지 어떻게 알 수 있을까
11. x, y좌표가 일치하는 사각형은 없다는 걸 명심하자

처음엔 위처럼 풀려고 했으나 생각보다 쉽지 않았다. 두 사각형이 겹쳐지는 부분에서, 같은 사각형인지, 다른 사각형 때문에 길이 막혀있는지 판단하는 부분이 어려웠다. 특히 처음에 생각했던 것 처럼, y 좌표 를 기준으로 사각형을 판단할 때, y로 한번 찍어보고, x 좌표를 또 한번 비교해야하기 때문에 시간 복잡도가 최소 $O(n^2)$ 로 됨과 동시에 효율적이지 못하다는 생각이 들어서 검색을 해봤더니 역시 다른 좋은 방법이 있었다.

그것은 좌표를 2배로 확장시켜서 분기점에서 원래라면 분기점을 판단하는 코드가 실행되어야하지만 그 과정 자체를 없앨 수 있다. 스케일이 2배 커진다고 해서 어떤 손해가 날 것 같지는 않다.

좌표를 2배 확장시키고 외곽라인을 기준으로 BFS 방법으로 최단거리를 찾는다.

sol1

맵을 2배로 확장 시킨 후 -1 을 찍는다.

import java.util.*;
class Solution {
    static class Rect{
		int x1,x2,y1,y2;
		
		public Rect(int x1, int y1, int x2, int y2) {
			this.x1 =x1;
			this.y1 =y1;
			this.x2 =x2;
			this.y2 =y2;
		}
	}
	static int x,y;
	static List<Rect> rectList;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
		int[][] map = new int[102][102];
        rectList = new ArrayList<>();
        for(int i=0; i<rectangle.length; 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 y=sy; y<=ey; y++) {
        		for(int x=sx; x<=ex; x++) {
        			map[y][x] = -1;
        		}
        	}
        	rectList.add(new Rect(sx,sy,ex,ey));
        }

        answer= bfs(map, characterX*2, characterY*2, itemX*2, itemY*2);
        return answer;
    }
    static int bfs(int[][] map, int x, int y, int tx, int ty) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {x, y, 1});
		map[y][x] = 1;
		while(!q.isEmpty()) {
			int[] p = q.poll();
			int px = p[0];
			int py = p[1];
			int move = p[2];
			
			if(px == tx && py == ty) {
				return (move/2);
			}
			
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				if(map[ny][nx] < 0 && isBoundary(nx,ny)) {
					map[ny][nx] = move+1;
					q.add(new int[] {nx, ny, move+1});
				}
			}
		}
		return -1;
	}
    static boolean isBoundary(int x, int y) {
		for(Rect r : rectList) {
			if(r.x1 < x && r.y1 <y && r.x2 > x && r.y2 > y) return false;
		}
		return true;
	}
}

sol2

링크텍스트

border 에는 1
inner 에는 2

만약 다음 그려지는 도형이 기존에 있던 도형이랑 겹치면, 2로 남겨둔다.

일단 맵 좌표를 받아서

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    static int[][] map;
    static int answer;
    //character->item(목표 포인트)
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        answer=0;
        
        //1) map을 만든다.
        map= new int[101][101];
        
        //2) 좌표에 따라 map에 값을 넣을건데, 테두리에만 1을 넣을것이다.(*좌표는 두배로)
        for(int i=0; i<rectangle.length; i++){
            fill(2*rectangle[i][0], 2*rectangle[i][1], 2*rectangle[i][2], 2*rectangle[i][3]);
        }
        
        //3) bfs로 테두리 따라 양쪽으로 가보고 min값 채택
        bfs(2*characterX, 2*characterY, 2*itemX, 2*itemY);
        
        return answer/2;
    }
    
    //x1,y1,x2,y2 => (x1,y1)~(x2,y1), (x1,y2)~(x2,y2), (x1,y1)~(x1,y2), (x2,y1)~(x2,y2)
    //편하게 x2 해준 좌표를 받는다.
    public void fill(int x1, int y1, int x2, int y2){
        for(int i=x1; i<=x2; i++){
            for(int j=y1; j<=y2; j++){
                if(map[i][j]==2) continue;
                map[i][j]=2;
                if(i==x1||i==x2||j==y1||j==y2){
                    map[i][j]=1;
                }
            }
        }
    }//fill
    
    static int[] dx= {-1, 0, 0, 1};
    static int[] dy= {0, -1, 1, 0};
    public void bfs(int startx, int starty, int itemx, int itemy){
        boolean[][] visited= new boolean[101][101];
        Queue<Integer> queue= new LinkedList<>();
        queue.add(startx);
        queue.add(starty);
        
        while(!queue.isEmpty()){
            int x= queue.poll();
            int y= queue.poll();
            
            for(int i=0; i<4; i++){
                int nx= x+dx[i];
                int ny= y+dy[i];
                if(!check(nx, ny)) continue; //범위 아웃
                if(map[nx][ny]!=1||visited[nx][ny]) continue;
                
                //map[nx][ny]==2이고 방문한적없음
                map[nx][ny]=map[x][y]+1;
                if(nx==itemx&&ny==itemy){ //목표점 도달
                    answer= (answer==0)? map[nx][ny]:Math.min(answer,map[nx][ny]);
                    continue;
                }
                visited[nx][ny]= true;
                queue.add(nx);
                queue.add(ny);
            }
        }
    }//bfs
    
    public boolean check(int x, int y){
        if(x<0||y<0||x>100||y>100) return false;
        return true;
    }
}