[JAVA] 아이템 줍기 - 프로그래머스[Lv.3]

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

프로그래머스

---

import java.util.*;
class Solution {
    static int[][] map = new int[101][101]; //2배
    static boolean[][] visit = new boolean[101][101];
    static int[][] move = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        for (int[] rec : rectangle) {
            fillEdge(rec[0]*2, rec[1]*2, rec[2]*2, rec[3]*2);
        }

        return bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
    }

    public int bfs(int cx, int cy, int ix, int iy) {
        Queue<Pos> queue = new LinkedList<>();
        queue.add(new Pos(cx, cy, 0));
        visit[cx][cy] = true;
        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            if(now.x == ix && now.y == iy) {
                return now.distance / 2;
            }
            for (int[] d : move) {
                int nx = now.x + d[0];
                int ny = now.y + d[1];
                if(nx < 0 || nx > 100 || ny < 0 || ny > 100 || map[nx][ny] != 1 || visit[nx][ny]) continue;

                queue.add(new Pos(nx, ny, now.distance + 1));
                visit[nx][ny] = true;
            }
        }
        return -1;
    }

    public void fillEdge(int startX, int startY, int endX, int endY) {
        for (int i = startX; i <= endX; i++) {
            for (int j = startY; j <= endY; j++) {
                if(map[i][j] != 2) { //다른 사각형의 내부가 아닌 경우
                    if (i == startX || i == endX || j == startY || j == endY) { //사각형의 변일 경우 1로 표시
                        map[i][j] = 1;
                        continue;
                    }
                }
                map[i][j] = 2; //다른 겹치는 사각형의 모서리 지우기 + 내부는 2로 채움
            }
        }
    }

    class Pos {
        int x; int y; int distance;

        Pos(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
}

💡 BFS

풀이

• 격자 최소 단위가 1인 경우, 안쪽으로 한 칸 들어간 모형을 구현할 때 오류 발생 가능
  • 격자 최소 단위를 0.5로 줄여 모서리의 두께를 2배 늘려 해결함
  • 대신 모든 좌표를 * 2 로 가공해야 하고, 마지막에 답을 출력할 때 /2 해줘야 함
• 최외곽 테두리를 결정하기 위해 fill을 사용함
  • 외곽 기준으로 채우고, 1칸씩 줄인만큼 삭제하며 테두리만 남겨놓음
  • ❗❗ 이때, 최외곽을 해주기 위해선 테두리를 그릴 자리가 이미 다른 사각형의 내부일 경우 그리지 않아야 함 ❗❗
    • ❗ 모서리와 내부 채우는 숫자를 다르게 설정해서 모서리 그리기 전에 다른 사각형 내부인지 먼저 검사 필요함!!
  • 이때 큐에 좌표 위치, 누적 거리를 객체로 저장해 사용하다 목표 위치가 나오면 누적값 반환

---

💡 모서리만 저장하는 방식을 떠올리는 게 어려웠음. 처음엔 fill로 안쪽을 파내 모서리만 남겨놓으려 했지만 그럼 최외곽만 남겨놓는게 불가능함 (사각형이 주어지는 순서에 따라 겹치는 모서리도 그대로 표현 됨)
→ 모서리와 나머지를 채우는 숫자를 다르게 하고, 모서리를 그리기 전 다른 사각형의 내부가 아닌지 판단해 줌으로써 외곽에 있는 모서리만 그릴 수 있게 해야 함