프로그래머스: 아이템 줍기(JAVA)

문제 설명

아이템 줍기 문제는 캐릭터가 주어진 사각형 테두리만을 따라 아이템을 찾아가는 최단 거리를 구하는 문제입니다. 주어진 사각형 영역을 따라 캐릭터가 이동해야 하며, 내부를 지나갈 수 없고, 테두리만을 따라 이동할 수 있습니다.

 

문제 해결 전략

1. 좌표 2배 확대: 문제에서 제시된 좌표를 2배로 확장하여 정확한 경로를 추적합니다. 이렇게 하면 테두리와 내부를 구분하기 용이해집니다.
2. BFS 탐색: 테두리만을 따라 최단 거리를 구하기 위해 BFS(너비 우선 탐색)를 사용합니다. BFS는 최단 경로를 찾는 데 유효한 알고리즘입니다.
3. 맵 설정: 각 사각형에 대해 내부는 2, 테두리는 1로 표시하여 BFS 탐색을 통해 테두리만을 탐색합니다.

 

코드 구현

import java.util.*;

class Solution {
    
    static int[][] map = new int[102][102];
    static boolean[][] visited = new boolean[102][102];
    static int[] dx = new int[] {-1, 1, 0, 0};
    static int[] dy = new int[] {0, 0, -1, 1};
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        // 사각형 정보를 이용해 맵을 설정
        for (int[] rect : rectangle) {
            int x1 = rect[0] * 2;
            int y1 = rect[1] * 2;
            int x2 = rect[2] * 2;
            int y2 = rect[3] * 2;
            
            for (int i = x1; i <= x2; i++) {
                for (int j = y1; j <= y2; j++) {
                    if (i == x1 || i == x2 || j == y1 || j == y2) {
                        if (map[i][j] != 2) map[i][j] = 1; // 테두리 설정
                    } else {
                        map[i][j] = 2; // 내부는 2로 설정
                    }
                }
            }
        }
        
        // BFS를 통해 최단 거리 계산
        return bfs(new int[] {characterX * 2, characterY * 2, 0}, new int[] {itemX * 2, itemY * 2});
    }
    
    static int bfs(int[] now, int[] goal) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(now);
        visited[now[0]][now[1]] = true;
        
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int nowX = arr[0];
            int nowY = arr[1];
            int count = arr[2];

            // 목표에 도달하면 거리를 반환
            if (nowX == goal[0] && nowY == goal[1]) return count / 2;

            // 상하좌우로 이동
            for (int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                // 테두리만 지나갈 수 있으며, 방문하지 않은 곳만
                if (map[nextX][nextY] != 1 || visited[nextX][nextY]) continue;
                if (nextX < 0 || nextX >= 102 || nextY < 0 || nextY >= 102) continue;

                visited[nextX][nextY] = true;
                queue.offer(new int[] {nextX, nextY, count + 1});
            }
        }
        
        // 목표에 도달할 수 없는 경우
        return -1;
    }
}

시간 복잡도

• 각전체 맵 크기는 최대 102 x 102이므로, 시간 복잡도는 O(N)