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

승래·2026년 3월 18일

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

요구사항

여러 사각형이 겹쳐있을 때 테두리만 이동 가능
캐릭터 위치에서 아이템 위치까지 최단거리를 구하는 문제

접근 방식

좌표 2배 확장 + BFS 로 풀었다.

왜 2배 확장이 필요한가?

원래 좌표에서 사각형이 겹칠 때:
→ 경계선이 한 사각형의 테두리이면서 다른 사각형의 내부가 되는
  애매한 좌표가 발생

2배 확장하면:
→ 겹치는 경계선 사이에 공간이 생겨서
  테두리와 내부가 명확하게 구분됨

핵심 아이디어

1. 모든 좌표를 2배 확장
2. 각 사각형을 순회하며
   - 테두리: map[p][q] = 1 (단, 이미 1이면 유지)
   - 내부: map[p][q] = 2 (단, 이미 1이면 건드리지 않음)
3. BFS로 map == 1인 곳만 이동
4. 최단거리 / 2 = 실제 거리

테두리/내부 처리 조건

테두리: map[p][q] == 0일 때만 1로 표시
(이미 다른 사각형의 테두리면 유지)
내부: 2로 표시
(이미 1이면 건드리지 않음 → 어차피 내부라 이동 불가)

코드

import java.util.*;

class Point {
    int x, y, dist;
    public Point(int x, int y, int dist) {
        this.x = x; this.y = y; this.dist = dist;
    }
}

class Solution {
    int[][] map = new int[101][101];
    boolean[][] visit = new boolean[101][101];
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};
    int answer = 0;

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        for (int[] rect : rectangle) {
            int x1 = rect[0]*2, y1 = rect[1]*2;
            int x2 = rect[2]*2, y2 = rect[3]*2;
            for (int p = x1; p <= x2; p++) {
                for (int q = y1; q <= y2; q++) {
                    if (p == x1 || p == x2 || q == y1 || q == y2) {
                        if (map[p][q] == 0) map[p][q] = 1;
                    } else {
                        map[p][q] = 2;
                    }
                }
            }
        }
        bfs(characterX*2, characterY*2, itemX*2, itemY*2);
        return answer;
    }

    public void bfs(int characterX, int characterY, int itemX, int itemY) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(characterX, characterY, 0));
        visit[characterX][characterY] = true;

        while (!q.isEmpty()) {
            Point p = q.poll();
            if (p.x == itemX && p.y == itemY) {
                answer = p.dist / 2;
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || ny < 0 || nx > 100 || ny > 100) continue;
                if (visit[nx][ny]) continue;
                if (map[nx][ny] == 1) {
                    visit[nx][ny] = true;
                    q.offer(new Point(nx, ny, p.dist + 1));
                }
            }
        }
    }
}