[프로그래머스] 아이템 줍기 (BFS, Java, lv3)

 

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

 

문제 풀이

- 격자형 그래프 문제 (BFS)

- rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태로 주어진다

- 직사각형 외곽 테두리를 통해 시작 (x, y) 에서 도착 (x,y) 까지 최단 거리를 구한다 

 

문제 예시1에서 (3,5) -> (4,5)로 가야하는데 (3,6)으로 가버려서 15(오답)이 나와 시간 소비를 많이 했다 (정답 17)

2차원 배열에 좌표가 한칸 단위로 붙어 있다보니 이를 어떻게 처리해야 할지 감이 잡히지 않았다

 

 

기술 블로그를 찾아보니 맵의 크기와 직사각형 크기를 모두 2배로 해서

문제가 되는 영역 사이에 공간이 생겨서 이동하지 않게 되었다 (아이디어가 기가 막히다, 삽질한 3시간 ㅠ)

 

주의할 부분은 시작 (x, y), 종료 (x,y) 좌표 값도 2배로 해야하고, 
직사각형 크기와 거리가 두 배가 되었기 때문에 결과값도 절반으로 나눠줘야 한다 

 

 

제출 코드 

좌표값과 직사각형 영역을 2배로 하고, 테두리 영역만 잘 구하면 나머지는 기본 BFS 로직으로 처리

import java.util.*;
class Solution {
    private static int ROW = 101;
    private static int COL = 101;
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] outside = getOutside(rectangle);
        return bfs(2 * characterX, 2 * characterY, 2 * itemX, 2 * itemY, outside);
    }
    
    private int bfs(int startX, int startY, int endX, int endY, int[][] outside) {
        Deque<Integer> que = new ArrayDeque<>();
        que.add(startX);
        que.add(startY);
        
        int[][] dist = new int[ROW][COL];
        for(int i = 0; i < ROW; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        dist[startX][startY] = 0;
        
        int[][] dir = {
            {0, 1},
            {0, -1},
            {1, 0},
            {-1, 0}
        };
        
        while(!que.isEmpty()) {
            int x = que.poll();
            int y = que.poll();
            
            for(int i = 0; i < 4; i++) {
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];
                
                if(dx < 0 || dy < 0 || dx >= ROW || dy >= COL) continue;
                if(outside[dx][dy] == 1 && dist[dx][dy] > dist[x][y] + 1) {
                    dist[dx][dy] = dist[x][y] + 1;
                    que.add(dx);
                    que.add(dy);
                }
            }
        }
    
        return (int) dist[endX][endY] / 2;
    }
   
    private int[][] getOutside(int[][] rectangle) {
        int[][] result = new int[ROW][COL];
        
        for(int[] rect: rectangle) {
            int x1 = rect[0] * 2;
            int y1 = rect[1] * 2;
            int x2 = rect[2] * 2;
            int y2 = rect[3] * 2;
            
            for(int i = x1; i <= x2; i++) {
                for(int j = y1; j <= y2; j++) {
                    if(result[i][j] == 2) continue; // 내부인 경우
                    
                    result[i][j] = 2; // 내부
                    
                    if(i == x1 || i == x2 || j == y1 || j == y2) result[i][j] = 1; // 외곽
                }
            }
        }
        
        return result;
    }

}