[prog 87694] 아이템 줍기

프로그래머스

 

import java.util.*;

class Solution {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    
    static class Point {
        int x, y, dist;
        
        Point(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    
    public int solution(int[][] rectangle, // 직사각형 좌표 목록
                        int characterX, int characterY, // 초기 캐릭터의 위치
                        int itemX, int itemY) // 아이템의 위치
    {
        // 맵 그리기
        // - 정확한 경계 처리를 위해 맵을 2배로 증가
        map = new int[101][101];
        visited = new boolean[101][101];
        for (int[] rect : rectangle) {
            int x1 = rect[0] * 2;
            int y1 = rect[1] * 2;
            int x2 = rect[2] * 2;
            int y2 = rect[3] * 2;
            
            // 테두리는 1로 설정
            // 내부는 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;
                    }
                }
            }
        }
        return bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
    }
    
    static int bfs(int characterX, int characterY, int itemX, int itemY) {
        Queue<Point> q = new LinkedList<>();
        
        // 1. 시작점 넣고 방문처리
        q.offer(new Point(characterX, characterY, 0));
        visited[characterX][characterY] = true;
        
        while (!q.isEmpty()) {
            Point p = q.poll();
            
            // 2. 도착시 BFS 종료
            if (p.x == itemX && p.y == itemY)  return p.dist / 2;
            
            // 3. 사방탐색하며 테두리 따라 진행
            for (int d = 0; d < 4; d++) {
                int nx = p.x + dx[d];
                int ny = p.y + dy[d];
               
                // 경계조건 위반 또는 이미 방문시 패스
                if (!inMap(nx, ny) || visited[nx][ny])  continue;
                
                if (map[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny, p.dist + 1));
                }
            }
        }
        return -1;
    }
    
    static boolean inMap(int x, int y) {
        return 0 <= x && x <= 100 && 0 <= y && y <= 100;
    }
}

 

1. 문제 요약

• 다각형 모양 지형에서 캐릭터가 목표 위치에 있는 아이템을 줍기 위해 이동하는 최소 거리를 찾는 문제입니다.
• 지형은 여러 직사각형의 조합으로 이루어져 있으며, 각 직사각형의 변은 x축과 y축에 평행합니다.
• 캐릭터는 이 다각형의 테두리(외곽)를 따라서만 이동할 수 있습니다.
• BFS(너비 우선 탐색)를 사용하여 최단 경로를 찾는 것이 효과적입니다.

 

2. 핵심 아이디어

1. 맵 초기화:
   • 직사각형 좌표를 입력받아 맵을 초기화합니다.
   • 직사각형의 테두리는 1로, 내부는 2로 설정하여 방문하지 않도록 합니다.
   • 직사각형의 좌표를 2배로 늘려서 경계 처리를 보다 정확하게 합니다.
2. BFS를 이용한 최단 경로 탐색:
   • BFS를 사용하여 캐릭터가 아이템 위치에 도달하는 최단 경로를 찾습니다.
   • 큐를 사용하여 현재 위치와 이동 거리를 저장합니다.
   • 상하좌우 네 방향으로 이동을 시도하며, 이동 가능한 위치를 큐에 추가하고 방문 처리를 합니다.
   • 목표 위치에 도달하면 현재까지의 이동 거리를 반환합니다.
3. 경계 체크:
   • 이동할 위치가 맵의 범위를 벗어나지 않는지 확인하는 함수를 사용하여 경계 체크를 수행합니다.

 

3. 출제의도

1. BFS(너비 우선 탐색) 활용 능력:
   • BFS를 통해 최단 경로를 찾는 문제 해결 능력을 평가합니다. BFS는 그래프 탐색 알고리즘 중 하나로, 최단 경로를 찾는 데 유용합니다.
2. 2차원 배열 및 맵 초기화:
   • 2차원 배열을 다루는 능력을 평가합니다. 특히, 경계를 정확히 처리하기 위해 맵을 초기화하고, 이를 바탕으로 탐색하는 능력을 테스트합니다.
3. 경계 및 조건 체크:
   • 문제에서 주어진 조건을 정확히 이해하고, 이를 구현에 반영하는 능력을 평가합니다. 예를 들어, 직사각형 내부는 방문하지 않도록 설정하는 것과 같은 조건을 처리하는 능력입니다.