아이템 줍기 (Java)

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

---

1. 문제 이해 및 접근 방식

✅ 문제 개요

• 2D 좌표 평면에서 사각형의 경로를 따라 이동하며 최단 거리로 아이템을 획득해야 함.
• 이동은 테두리(경계선)에서만 가능하며, 사각형 내부로는 진입할 수 없음.
• 최단 거리 경로를 찾아야 하므로 BFS(너비 우선 탐색)이 적절하지만, 본 코드에서는 DFS(깊이 우선 탐색)을 사용하여 경로를 탐색함(시간이차이가 크지 않다고 생각).

---

2. 초기 접근 방식 (실패 원인 포함)

🚨 1차 시도: 직사각형 내부의 공간을 모두 지나갈 수 없음으로 처리(HashSet 사용)

    Set<String> insidePoint = new HashSet<>();

• 문제의 좌표 범위가 1 ≤ x, y ≤ 50 이므로 boolean[][] 배열을 선언하고 사각형을 표시함.
• 하지만 이 방식에서는 사각형 테두리와 내부를 정확히 구분할 수 없음.
• 예를 들어, (3,5)에서 (4,5)로 이동해야 하는데, 배열 상에서는 (3,6)도 이동할 수 있는 곳으로 판단하는 오류 발생.

🚨 2차 시도: TreeSet을 사용하여 정답으로 추출되는 모든 값 저장

Set<String> answers = new TreeSet<>();

• 정답으로 나오는 모든 값들을 Set에 저장시키고 가장 큰 두번째를 뽑게되면 정답이라고 생각
  • 아이템까지 가는 거리는 총 두가지이고 1차 시도에 대한 예외에 대한 값들은 모두 더 빠를 것이라고 생각
• 하지만 이 방식은 예제 2번과 같은 경로에서 오작동(더 느린 경우가 발생)하는 반례가 발생하여 실패.

---

3. 최종 해결 방법: 좌표 크기 확장 (2배 확대)

🔹 핵심 아이디어

1. 맵의 기본 눈금을 1×1이 아닌 2×2로 변경

   • 각 좌표를 2배 확장하여 계산하면, 사각형의 테두리와 내부 영역을 확실하게 구분할 수 있음.
   • 예를 들어 (1,1)에 위치한 사각형은 (2,2) ~ (4,4)로 변환됨.

2. 확장된 좌표를 기반으로 boolean[][] map을 생성

   • 경계를 테두리로만 설정하여 이동 가능하도록 처리.
   • 사각형 내부를 방문하지 못하도록 Set<String>을 활용하여 내부 좌표를 따로 저장.

3. DFS(깊이 우선 탐색)로 최단 경로 탐색

   • 방문한 좌표를 체크하며, 아이템 위치에 도달하면 최단 거리 갱신.

---

4. 최종 코드 (Java)

import java.util.*;

class Solution {
    
    Set<String> insidePoint = new HashSet<>();
    StringBuilder sb = new StringBuilder();
    boolean[][] map = new boolean[111][111];
    boolean[][] visited = new boolean[111][111];
    int answer = Integer.MAX_VALUE;

    // 방향 벡터 (상, 우, 하, 좌)
    int[] dix = {-1, 0, 1, 0};
    int[] diy = {0, 1, 0, -1};

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        // 좌표 크기 2배 확장
        characterX *= 2;
        characterY *= 2;
        itemX *= 2;
        itemY *= 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 + 1; x <= x2 - 1; x++) {
                for (int y = y1 + 1; y <= y2 - 1; y++) {
                    sb.append(x).append(",").append(y);
                    insidePoint.add(sb.toString());
                    sb.setLength(0);
                }
            }

            // 사각형 테두리 좌표를 이동 가능하도록 설정
            for (int j = x1; j <= x2; j++) {
                map[j][y1] = true;
                map[j][y2] = true;
            }
            for (int j = y1; j <= y2; j++) {
                map[x1][j] = true;
                map[x2][j] = true;
            }
        }

        // DFS 탐색 시작
        visited[characterX][characterY] = true;
        dfs(characterX, characterY, 0, itemX, itemY);

        return answer / 2; // 최단 거리 반환 (2배 확장한 값이므로 다시 2로 나눔)
    }

    private void dfs(int cx, int cy, int cnt, int ix, int iy) {
        if (cx == ix && cy == iy) {
            answer = Math.min(answer, cnt);
        }

        for (int i = 0; i < 4; i++) {
            int dx = cx + dix[i];
            int dy = cy + diy[i];

            if (dx < 0 || dy < 0 || dx >= 111 || dy >= 111) continue;
            if (visited[dx][dy]) continue;
            if (!map[dx][dy]) continue;

            sb.append(dx).append(",").append(dy);
            String tmp = sb.toString();
            sb.setLength(0);

            if (insidePoint.contains(tmp)) continue;

            visited[dx][dy] = true;
            dfs(dx, dy, cnt + 1, ix, iy);
            visited[dx][dy] = false;
        }
    }
}

---

5. 시간 복잡도 분석

✅ 공간 복잡도

• map[][] 및 visited[][] 배열 크기: O(111 × 111) ≈ O(1)
• insidePoint 저장 공간: O(N), (N: 사각형 내부 좌표 수)

✅ 시간 복잡도

• DFS 탐색: 최악의 경우 O(4^N) 이지만, 백트래킹 및 방문 체크로 O(N^2) 수준으로 최적화됨.
• 사각형 테두리 및 내부 좌표 설정: O(N)
• 총 시간 복잡도: O(N^2) (N ≤ 100이므로 충분히 실행 가능)

---

📌 핵심 포인트

• 좌표 크기 2배 확장하여 경계와 내부를 정확히 구분.
• DFS 탐색으로 최단 경로 탐색 (answer / 2 처리).
• Set<String>을 활용하여 내부 진입 방지.