[Programmers] 아이템 줍기 JAVA

반응형

728x90

[Programmers] 아이템 줍기 - LV 3

---

접근

• bfs

---

풀이

좌표 평면에 여러 개의 사각형이 주어지고 겹쳐진 사각형의 외부 테두리만 따라 이동하며 아이템을 주우러 갈 때 최단 경로를 구하는 문제이다. 

출처: Programmers

간단하게 생각하자면 모든 사각형의 테두리만 2차원 배열에 매핑한 뒤 매핑된 경로만 bfs를 사용해 따라가면 된다. 문제는 좌표를 그대로 가져 쓰면 (4, 5) (4, 6)처럼 움푹 들어간 부분을 제대로 표시할 수 없다. 각 좌표마다 점을 찍어 매핑하기 때문에 (3, 5)와 (3, 6) 은 좌표상에서 붙어있는 것처럼 보이기 때문에 정확하게 구현을 하기 위해선 좌표를 두 배로 확장해주어야 한다. 

    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};
    
    private static class Location {
        public final int x;
        public final int y;
        public final int step;
        
        public Location(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }

객체를 사용해 bfs를 수행했으므로 사용할 객체를 정의해 줬다. 

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] matrix = new int[102][102];
        
        for (int[] rect : rectangle) {
            int leftX = rect[0] * 2;
            int leftY = rect[1] * 2;
            int rightX = rect[2] * 2;
            int rightY = rect[3] * 2;

            for (int x = leftX; x <= rightX; x++) {
                matrix[x][leftY] = 1;
                matrix[x][rightY] = 1;
            }

            for (int y = leftY; y <= rightY; y++) {
                matrix[leftX][y] = 1;
                matrix[rightX][y] = 1;
            }
        }
        
        for (int[] rect : rectangle) {
            int leftX = rect[0] * 2;
            int leftY = rect[1] * 2;
            int rightX = rect[2] * 2;
            int rightY = rect[3] * 2;

            for (int i = leftX + 1; i < rightX; i++) {
                for (int j = leftY + 1; j < rightY; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

2배로 확장한 2차원 배열에 모든 사각형의 테두리를 매핑한 뒤 겹치는 내부 부분들을 0으로 다 지워줬다. 

	Queue<Location> que = new LinkedList<>();
        boolean[][] isVisited = new boolean[102][102];
        que.offer(new Location(characterX * 2, characterY * 2, 0));
        isVisited[characterX * 2][characterY * 2] = true;
        
        while(!que.isEmpty()) {
            Location location = que.poll();
            
            if(location.x == (itemX * 2) && location.y == (itemY * 2)) {
                return location.step / 2;
            }
            
            for(int d = 0; d < 4; d++) {
                int nx = location.x + dx[d];
                int ny = location.y + dy[d];
                
                if(nx < 0 || nx >= matrix.length || ny < 0 || ny >= matrix[nx].length)
                    continue;
                
                if(matrix[nx][ny] == 0 || isVisited[nx][ny])
                    continue;
                
                que.offer(new Location(nx, ny, location.step + 1));
                isVisited[nx][ny] = true;
            }
        }
        
        return 0;
    }

좌표를 만들었다면 만들어진 좌표를 통해 bfs를 수행해 주면 최단 경로를 구할 수 있다. 

---

전체 코드

import java.util.*;

class Solution {
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};
    
    private static class Location {
        public final int x;
        public final int y;
        public final int step;
        
        public Location(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] matrix = new int[102][102];
        
        for (int[] rect : rectangle) {
            int leftX = rect[0] * 2;
            int leftY = rect[1] * 2;
            int rightX = rect[2] * 2;
            int rightY = rect[3] * 2;

            for (int x = leftX; x <= rightX; x++) {
                matrix[x][leftY] = 1;
                matrix[x][rightY] = 1;
            }

            for (int y = leftY; y <= rightY; y++) {
                matrix[leftX][y] = 1;
                matrix[rightX][y] = 1;
            }
        }
        
        for (int[] rect : rectangle) {
            int leftX = rect[0] * 2;
            int leftY = rect[1] * 2;
            int rightX = rect[2] * 2;
            int rightY = rect[3] * 2;

            for (int i = leftX + 1; i < rightX; i++) {
                for (int j = leftY + 1; j < rightY; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        Queue<Location> que = new LinkedList<>();
        boolean[][] isVisited = new boolean[102][102];
        que.offer(new Location(characterX * 2, characterY * 2, 0));
        isVisited[characterX * 2][characterY * 2] = true;
        
        while(!que.isEmpty()) {
            Location location = que.poll();
            
            if(location.x == (itemX * 2) && location.y == (itemY * 2)) {
                return location.step / 2;
            }
            
            for(int d = 0; d < 4; d++) {
                int nx = location.x + dx[d];
                int ny = location.y + dy[d];
                
                if(nx < 0 || nx >= matrix.length || ny < 0 || ny >= matrix[nx].length)
                    continue;
                
                if(matrix[nx][ny] == 0 || isVisited[nx][ny])
                    continue;
                
                que.offer(new Location(nx, ny, location.step + 1));
                isVisited[nx][ny] = true;
            }
        }
        
        return 0;
    }
}