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

문제 소개

 

오늘 풀었던 아이템 줍기 - 프로그래머스 문제를 정리합니다.
이 문제는 다각형 형태로 구성된 지형의 외곽 경로를 따라 캐릭터가 아이템까지 최단거리로 이동하는 경로를 찾는 BFS 탐색 문제입니다.
문제는 "지형 외곽 경로만 유효한 이동 경로로 인정"된다는 점이며, 이를 구현하기 위해 좌표 확대 + 내부 제거 기법을 사용했습니다.

문제 링크: 아이템 줍기 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 전체 좌표를 2배로 확장하여 절반 좌표(테두리 경로 표현)를 정확히 표현 가능하게 만듦
2. 모든 직사각형 경로를 우선 1로 채움
3. 이후 내부 영역을 -1로 마스킹하여 외곽 테두리만 남김 (0으로 해도 상관없음)
4. 외곽 경로만을 대상으로 BFS 탐색하여 최단 거리 계산

---

해결 과정 및 코드

핵심 아이디어

1. 좌표를 2배로 확장하여 테두리를 표현할 수 있음
2. 모든 직사각형을 포함하는 범위를 board에 1로 마킹
   → 이후 내부는 -1로 덮어서 외곽만 1로 유지
3. BFS로 외곽 경로를 따라 최단거리 탐색
   → 좌표가 아이템 위치에 도달하면 거리 반환
4. board 값이 1인 경우만 유효한 경로로 인정

코드

시간 복잡도 : O(NM)

import java.util.*;

class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int size = 102;
        int [][] board = new int[size][size];
        int [][] delta = {{1, 0},{-1, 0},{0, 1},{0, -1}};
        
        // 1. 좌표를 2배 확장
        for (int [] rect : rectangle) {
            int x1 = rect[0] * 2, y1 = rect[1] * 2;
            int x2 = rect[2] * 2, y2 = rect[3] * 2;
            for (int x = x1; x <= x2; x++) {
                for (int y = y1; y <= y2; y++) {
                    board[x][y] = 1;                    
                }
            }
        }

        // 2. 내부를 -1로 덮어서 테두리만 남기기
        for (int [] rect : rectangle) {
            int x1 = rect[0] * 2, y1 = rect[1] * 2;
            int x2 = rect[2] * 2, y2 = rect[3] * 2;
            for (int x = x1 + 1; x < x2; x++) {
                for (int y = y1 + 1; y < y2; y++) {
                    board[x][y] = -1;                    
                }
            }
        }

        // 3. BFS로 최단거리 탐색
        Queue<int[]> que = new ArrayDeque<>();
        que.offer(new int[] {characterX*2, characterY*2, 0});
        board[characterX*2][characterY*2] = -2;

        while (!que.isEmpty()) {
            int[] cur = que.poll();
            int x = cur[0], y = cur[1], dist = cur[2];

            if (x == itemX * 2 && y == itemY * 2) return dist / 2;

            for (int[] d : delta) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue;
                if (board[nx][ny] != 1) continue;
                board[nx][ny] = -2; // 로깅
                que.offer(new int[]{nx, ny, dist + 1});
            }
        }

        return -1;
    }
}