[프로그래머스 알고리즘 고득점 Kit][깊이/너비 우선 탐색(DFS/BFS)][Java] 아이템 줍기

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

프로그래머스

 

초기에 메서드도 분리하고 깔끔하게 쓰려고 분리할 거 다하다가
복잡해지고... 디버깅도 쉽지 않았다.

1. 복잡한 코드

일단 메인 아이디어는 주어진 사각형의 테두리를 남겨두고 bfs로 탐색하면서 거리를 업데이트 해주는 것이다.

주의했어야하는 부분은 expandedCordinate 메서드 위 주석에 나온 것처럼
1111
1111 이렇게 주어진 사각형 내부 공백이 없어서 테두리만 남길 수 없었기에
스케일을 키우는 작업을 했어야했습니다.

import java.util.*;

class Solution {

    int[][] expandedRectangle;
    int expandedCharacterX;
    int expandedCharacterY;
    int expandedItemX;
    int expandedItemY;
    final int SIZE = 105;
    int[][] map;
    int[][] dist;
    final int[] dx = {-1, 1, 0, 0};
    final int[] dy = {0, 0, -1, 1};
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        map = new int[SIZE][SIZE];
        dist = new int[SIZE][SIZE];
        
        expandCordinate(rectangle, characterX, characterY, itemX, itemY);
        clearInsideOfFrame(expandedRectangle);
        
        return bfs(expandedCharacterX, expandedCharacterY, expandedItemX, expandedItemY) / 2;
    }

    //1111
    //1111 이런 사각형이 있다고 생각하면 중간 공백이 없어서
    //테두리와 내부를 분리할 수 없음, 그래서 모든 좌표를 2배함으로써 중간 공백을 만들어줌
    public void expandCordinate(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        expandedRectangle = new int[rectangle.length][4];

        expandedCharacterX = 2 * characterX;
        expandedCharacterY = 2 * characterY;
        expandedItemX = 2 * itemX;
        expandedItemY = 2 * itemY;
        for(int i=0; i<rectangle.length; i++){
            expandedRectangle[i][0] = 2 * rectangle[i][0];
            expandedRectangle[i][1] = 2 * rectangle[i][1];
            expandedRectangle[i][2] = 2 * rectangle[i][2];
            expandedRectangle[i][3] = 2 * rectangle[i][3];
        }
    }
    public void fillRectangle(int[][] rectangle) {

        for(int[] r : rectangle) {
            fillMap(r[0], r[1], r[2], r[3], 1);
        }
    }
    public void clearInsideOfFrame(int[][] rectangle) {
        fillRectangle(rectangle);
        
        for(int[] r : rectangle) {
            fillMap(r[0]+1, r[1]+1, r[2]-1, r[3]-1, 0);
        }
    }
    public void fillMap(int x1, int y1, int x2, int y2, int fillNum) {
        for(int x=x1; x<=x2; x++) {
            for(int y= y1; y<=y2; y++) {
                map[x][y] = fillNum;
            }
        }
    }
    public int bfs(int startX, int startY, int targetX, int targetY) {
        for(int i=0; i<SIZE; i++) {
            Arrays.fill(dist[i], -1);
        }
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {startX, startY});
        dist[startX][startY] = 0;
        while(!q.isEmpty()) {
            int[] curr = q.poll();
            int x = curr[0];
            int y = curr[1];
            
            if(x == targetX && y == targetY) return dist[x][y];
            
            for(int d=0; d<4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if(nx < 0 || nx >= SIZE || ny < 0 || ny >= SIZE) continue;
                if(map[nx][ny] == 0) continue;
                if(dist[nx][ny] != -1) continue;
                
                q.add(new int[] {nx, ny});
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
        return -1;
    }
}

2. 지피티한테 클린하게 바꾸면 어떻게 되냐 물어봤을 때 코드

스케일을 키운 사각형 배열은 필요 없다고 생각하긴했는데
없으니 확실히 깔끔해졌네요
제 코드를 레퍼런스로 보냈으니 결과는 그렇게 큰 차이가 없다고 생각합니다.

import java.util.*;

class Solution {

    private static final int SIZE = 105;
    private static final int SCALE = 2;
    private static final int ROAD = 1;
    private static final int EMPTY = 0;

    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    private final int[][] map = new int[SIZE][SIZE];

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        buildBorderMap(rectangle);

        int startX = scale(characterX);
        int startY = scale(characterY);
        int targetX = scale(itemX);
        int targetY = scale(itemY);

        return bfs(startX, startY, targetX, targetY) / SCALE;
    }

    private void buildBorderMap(int[][] rectangles) {
        paintAreas(rectangles);
        eraseInnerAreas(rectangles);
    }

    private void paintAreas(int[][] rectangles) {
        for (int[] r : rectangles) {
            fill(
                    scale(r[0]),
                    scale(r[1]),
                    scale(r[2]),
                    scale(r[3]),
                    ROAD
            );
        }
    }

    private void eraseInnerAreas(int[][] rectangles) {
        for (int[] r : rectangles) {
            fill(
                    scale(r[0]) + 1,
                    scale(r[1]) + 1,
                    scale(r[2]) - 1,
                    scale(r[3]) - 1,
                    EMPTY
            );
        }
    }

    private void fill(int x1, int y1, int x2, int y2, int value) {
        for (int x = x1; x <= x2; x++) {
            for (int y = y1; y <= y2; y++) {
                map[x][y] = value;
            }
        }
    }

    private int bfs(int startX, int startY, int targetX, int targetY) {
        int[][] dist = new int[SIZE][SIZE];

        for (int i = 0; i < SIZE; i++) {
            Arrays.fill(dist[i], -1);
        }

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});
        dist[startX][startY] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            if (x == targetX && y == targetY) {
                return dist[x][y];
            }

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (isOutOfRange(nx, ny)) {
                    continue;
                }

                if (map[nx][ny] != ROAD) {
                    continue;
                }

                if (dist[nx][ny] != -1) {
                    continue;
                }

                dist[nx][ny] = dist[x][y] + 1;
                queue.add(new int[]{nx, ny});
            }
        }

        return -1;
    }

    private boolean isOutOfBounds(int x, int y) {
        return x < 0 || y < 0 || x >= SIZE || y >= SIZE;
    }

    private int scale(int value) {
        return value * SCALE;
    }
}