[JAVA] 아이템 줍기

NoHae·2025년 3월 6일

코딩테스트

프로그래머스_코딩테스트

목록 보기

43/51

문제 출처

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 아이템 줍기
https://school.programmers.co.kr/learn/courses/30/lessons/87694

문제 설명

캐릭터의 초기 좌표 characterX, characterY,
아이템의 위치 itemX, itemY
사각형들의 좌표 2차원 배열 rectangle이 주어질 때,

캐릭터가 아이템을 얻기 위해 이동해야하는 가장 짧은 거리를 return 하라.

접근 방법

사각형이 그려진 map을 2차원 배열을 통해 나타낸다.
이 때, 주어진 직사각형은 좌표 상으로 담겨 있고, 실제 선이 아니므로, 문제가 발생할 수 있으므로 map은 좌표 x2 하여 나타낸다.(알게된 점 참고)

이 후, 좌표를 상하좌우 움직이며 이동 가능한지 BFS를 통해 확인한다.
이동이 가능하면 해당 거리를 이전 거리 + 1을 하여 표기한 뒤, 큐에 삽입하여 도착할 때까지 진행한다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    
    static int[][] map;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    static int answer;
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        map = new int[101][101];
        
        for (int[] r : rectangle)fill(2*r[0],2*r[1],2*r[2],2*r[3]); // 좌표 2배로 확장
        
        bfs(2*characterX,2*characterY,2*itemX,2*itemY);// BFS 실행
        
        return answer;
    }

    public void fill(int x1, int y1, int x2, int y2){
        
        for (int i = x1; i<=x2; i++){
            for (int j = y1; j<=y2; j++){
                
                if (map[i][j] == 2)continue; // 이미 내부를 2로 설정한 경우 pass
                
                map[i][j] = 2; // 내부의 경우 2로 설정
                
                if (i==x1||i==x2||j==y1||j==y2)map[i][j] = 1; // 직사각형의 테두리들은 1로 설정
                
            }
        }
    }

    public void bfs(int startX, int startY, int itemX, int itemY){
        
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startX,startY});
        int[][] cost = new int[101][101]; // 각 위치까지의 거리 배열
        cost[startX][startY] = 1; // 시작 위치 (거리 초기화)

        while (!q.isEmpty()){
            
            int[] move = q.poll();

            for (int i = 0; i < 4; i++){
                
                int moveX = move[0] + dx[i]; // 이동 가능한 경우 모두 확인
                int moveY = move[1] + dy[i];

                if (validation(moveX,moveY))continue; // 범위 벗어나면 스킵

                if (map[moveX][moveY] == 1 && cost[moveX][moveY] == 0){ // 테두리만 이동 가능 + 지나가지 않은 곳만 거리 확인
                    
                    cost[moveX][moveY] = cost[move[0]][move[1]]+1; // 거리 업데이트
                    q.offer(new int[]{moveX, moveY});
                    
                }
            }
        }
        
        answer = cost[itemX][itemY]/2; // 2배 확장했으므로 원래 크기로 변환
    }

    public boolean validation(int x, int y){
        
        return (0>x || 0>y || x>100 ||y>100); // 좌표가 범위 벗어날 경우 true 반환
    
    }
}

Review

import java.util.*;

class Solution {
    
    static int[][] map;
    static int[][] cost;
    static int SIZE;
    
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    
    public void fill(int[][] rectangle){ // 사각형의 테두리를 map에 표시
        
        for(int[] k : rectangle){
            int x1 = k[0]*2, x2 = k[2]*2;
            int y1 = k[1]*2, y2 = k[3]*2;
            
            for(int i = x1; i<=x2; i++){
                for(int j = y1; j<=y2; j++){
                    if(map[i][j] == 2) continue;
                    map[i][j] = 2; // 내부의 경우 2로설정
                    if(i == x1 || i == x2 || j == y1 || j == y2) map[i][j] = 1; // 테두리의 경우 1로 설정
                }
            }
        }
    }
    
    public int bfs(int startX, int startY, int endX, int endY){
        Queue<int[]> q =new LinkedList<>();
        q.add(new int[]{startX, startY});
        cost[startX][startY] = 1;
        
        while(!q.isEmpty()){
            int[] point = q.poll();
            int x = point[0];
            int y = point[1];
            for(int i = 0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >= 102 || ny >= 102 || nx < 0 || ny < 0) continue;
                
                if(cost[nx][ny] == 0 && map[nx][ny] == 1) {
                    cost[nx][ny] = cost[x][y] + 1;
                    q.offer(new int[]{nx,ny});
                }
            }
        }
        
        return cost[endX][endY]/2;
        
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        SIZE = 102;
        map = new int[SIZE][SIZE];
        cost = new int[SIZE][SIZE];
        
        fill(rectangle);
        int answer = bfs(characterX*2, characterY*2,itemX*2,itemY*2);
        
        return answer;
        
        
    }
    
}

알게된 점

해당 문제는 잘 풀지 못해서 다른 사람의 풀이를 참고했다. 참고하는 과정에서 왜 좌표를 2배하는 가에 대한 이해가 가장 오래 걸렸다.

문제는 예시 그림의 선을 통해 어떤 방식으로 직사각형이 생겼는지 주어진다. 하지만 실제로는 좌표로만 주어지고, 그림은 임의로 그린 사각형이기 때문에, 선으로 이어지지 않았지만, 테두리라고 인식이 가능하여 빈 공간을 뚫고 지나 갈 수 있다.
따라서 좌표를 2배하여 해당 그림처럼 실제로 이어지지 않았지만 좌표상 붙어있는 경우를 대비할 수 있다.