프로그래머스 Level 3 – 아이템 줍기(Java, BFS + 테두리 따라가기)

🎒 프로그래머스 Level 3 – 아이템 줍기(Java, BFS + 테두리 따라가기)

이번 문제는 프로그래머스에서 난이도와 구현 난이도가 꽤 있는 편인 ‘아이템 줍기’ 문제다.
직사각형 여러 개가 겹쳐 있는 지도 위에서 테두리만 따라 이동하여 캐릭터가 아이템까지 최단 거리로 도달하는 경로 길이를 구하는 문제.

이 문제의 핵심은 단 하나다.

❗ 직사각형 내부로 들어가면 안 되고,
❗ 테두리만 따라 이동해야 하며,
❗ 겹침/교차 때문에 지도 해상도를 2배로 늘려서 정밀도를 확보해야 한다.

그렇다.
기본 BFS처럼 보이지만, 실제로는 “테두리 구분을 위해 좌표를 2배 확대하는” 아이디어가 있어야 제대로 풀 수 있다.

---

📌 문제 핵심 아이디어

✔ 1. 좌표를 2배로 키워서 정밀도 확보

겹치는 사각형 영역이 많기 때문에 실제 좌표에서 움직이면
대각선으로 잘못 지나가거나 테두리 판별이 깨지는 문제가 발생한다.
그래서 모든 좌표를 ×2 해주고 맵 전체 크기를 102×102 정도로 잡는다.

✔ 2. map[][]에 테두리 채우기

각 rectangle에 대해:

• 전체 영역을 map=1 로 먼저 채워놓고
• 내부 영역을 다시 map=0 으로 지워서
  👉 테두리만 map=1 상태로 만든다.

✔ 3. BFS로 테두리만 이동

• 방문 배열 vist[][]로 중복 방지
• 캐릭터 시작 위치와 아이템 위치 역시 ×2
• BFS로 최단 거리 탐색
• 최종 거리 값은 /2 해서 원래 좌표 거리로 변환

선 굵게 설명하면 **정밀도 확보(2배)**가 핵심,
나머지는 전형적인 BFS다.

---

🧩 자바 코드(BFS 구현)

 

import java.util.*;

class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        int[][] map = new int[102][102];
        boolean[][] vist = new boolean[102][120];
        
        int[] dx = new int[]{1,0,-1,0};
        int[] dy = new int[]{0,1,0,-1};
        
        // 1. 전체 영역을 먼저 1로 채우기 (2배 스케일)
        for(int[] r : rectangle){
            int x1 = r[0] * 2;
            int y1 = r[1] * 2;
            int x2 = r[2] * 2;
            int y2 = r[3] * 2;
            
            for(int i = x1; i <= x2; i++){
                for(int j = y1; j <= y2; j++){
                    map[i][j] = 1;
                }
            }
        }
        
        // 2. 내부는 0으로 채워서 테두리만 남기기
        for(int[] r : rectangle){
            int x1 = r[0] * 2;
            int y1 = r[1] * 2;
            int x2 = r[2] * 2;
            int y2 = r[3] * 2;

            for(int i = x1 + 1; i < x2; i++){
                for(int j = y1 + 1; j < y2; j++){
                    map[i][j] = 0;
                }
            }
        }
        
        // 3. BFS 탐색
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{characterX * 2, characterY * 2, 0});
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0], y = cur[1], dist = cur[2];
            
            // 도착하면 /2 해서 반환
            if(x == itemX * 2 && y == itemY * 2) return dist / 2;
            
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || nx > 100 || ny < 0 || ny > 100) continue;
                if(!vist[nx][ny] && map[nx][ny] == 1){
                    q.add(new int[]{nx, ny, dist + 1});
                    vist[nx][ny] = true;
                }
            }
        }
        return answer;
    }
}

---

🔍 코드 해설

✔ 2배 스케일링

대각선으로 테두리끼리 맞닿는 경우,
원래 좌표에서는 갈 수 없는 길을 갈 수 있는 것처럼 보이는 버그가 생기는 걸 막기 위한 필수 작업.

✔ 테두리 생성 로직

• rectangle 전체를 먼저 1로 칠한다
• 그 안쪽만 다시 0으로 싹 지운다
  ⬇
  결국 가장 바깥 선만 남는다.

✔ BFS로 shortest path 탐색

맵 크기가 크지 않기 때문에 BFS로 충분.

✔ dist / 2

좌표를 2배로 늘렸기 때문에 이동 거리도 두 배가 됨 → 2로 나누어 원래 거리로 환산.

---

🎯 최종 정리

이 문제의 핵심은 BFS가 아니라 지도 구성(테두리 생성)이다.
정확하게 테두리를 식별해야만 BFS가 정상적으로 작동하며,
그걸 위해 좌표를 2배로 스케일링하는 것이 정답의 포인트다.

• 좌표 2배 스케일
• 테두리만 map=1
• BFS로 최단 거리
• 결과는 /2

이 네 가지를 기억하면 된다.