프로그래머스 Lv3 아이템 줍기

손정민·2024년 1월 14일

위의 그림처럼 직사각형의 겉테두리만 이동할 수 있다고하면

빨간 네모(출발 위치)
파란 원(아이템의 위치)
출발 위치에서 아이템까지의 최단거리를 구하는 말은 간단한 문제다.

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

입출력 예시

로직 설계

테두리의 값을 맵에 표시해둔다 (최대 맵의 크기 = 50)
-> 맵의 크기를 2배 키워서 진행함

bfs로 시작 지점부터 아이템의 좌표까지 거리를 구한다.

static 변수

        static int[][] map = new int[101][101];
        static int[][] distance = new int[101][101];
        static boolean[][] visited = new boolean[101][101];
        static int[] dh = {-1, 0, 0, 1};
        static int[] dw = {0, -1, 1, 0};

메인 함수

        public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
            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]);
            }
            checkDistance(new Point(2*characterY, 2*characterX), 
            				new Point(2*itemY, 2*itemX));
                            
            return distance[2*itemY][2*itemX]/2;
        }

fill 메소드

// 각 직사각형의 크기만큼 2로 값을 대입하다가 테두리를 의미하는 끝의 좌표 (x1, x2, y1, y2) 일 때에는 1로 값을 대입 
private void fill(int x1, int y1, int x2, int y2){
            for(int i=y1; i<=y2; i++){
                for(int j=x1; j<=x2; j++){
                    if(map[i][j]==2) continue;
                    map[i][j]=2;
                    if(i==y1||i==y2||j==x1||j==x2){
                        map[i][j]=1;
                    }
                }
            }
        }

예시 1 fill메소드 실행 결과

checkDistance 메소드

// 일반적인 4방향 BFS 코드이다.
private static void checkDistance(Point character, Point item) {
    Queue<Point> queue = new LinkedList<>();
    queue.offer(character);
    visited[character.x][character.y] = true;
    while (!queue.isEmpty()) {
        Point p = queue.poll();
        if(p.x == item.x && p.y == item.y) break;
        for (int i = 0; i < 4; i++) {
            int nextH = p.x + dh[i];
            int nextW = p.y + dw[i];
            if (nextH >= 0 && nextW >= 0 && nextH <= 100 && nextW <= 100) {
                if (!visited[nextH][nextW] && map[nextH][nextW] == 1) {
                    visited[nextH][nextW] = true;
                    distance[nextH][nextW] = distance[p.x][p.y] + 1;
                    queue.offer(new Point(nextH, nextW));
                }
            }
        }
    }
}