🔍 Problem

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

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

나. 접근 방법
매트릭스와 dist 배열의 크기를 2배로 늘리고 바깥쪽 테두리는 1, 안쪽은 2로 채우는 방식으로 바깥쪽 테두리만 1로 만들어 BFS를 실시한다.

다. 문제 유형
BFS 그리고 구현

---

📒 수도 코드

가. [구현] 주어진 rectangle들로 바깥쪽 테두리를 구한다.
바깥쪽 테두리는 2차원 배열로 1의 값으로 초기화하고, 안쪽은 2로 초기화한다. 이 부분이 상당히 중요하다. 만약 처음에 이렇게하고 다음 사각형을 2차원 배열에 초기화 시킬 시, 2를 만나면 그냥 그대로 납두고 2가 아닌 다른 값일 때, 2로 바꾸고 나서(선행) 해당 부분이 테두리이면 1로 초기화하는 방식으로 풀어야한다.

2로 바꾸고 나서(선행)가 선행되어지는 이유
2가 아닌 다른 값, 0이나 1이여도 일단 2로 바꿔주고 나중에 테두리를 구하는 방식이기 때문이다. 그리고 앞에 2이면 스킵하기 때문에 다른 도형의 내부는 아예 접근을 하지 않는다. 이러한 방식으로 도형의 외부 테두리에만 접근을 할 수 있는 것이다.

나. [BFS] 시작하는 시점의 x2에서 BFS 그래프 탐색을 실시한다.
2차원 배열로 하는 이유는 아래 같은 상황을 방지 하기 위해서이다.

(출처 : https://siino.tistory.com/23)

해당 부분은 일반적인 BFS와 동일하지만 nx와 ny를 조금 더 신경써줘야한다.

---

💻 Code

import java.util.*;

class Solution {
    static int[][] mat;
    static int[][] dist;
    
    void fill(int[] r){
        int x1 = r[0];
        int y1 = r[1];
        int x2 = r[2];
        int y2 = r[3];
        
        for(int i=2*y1 ; i<=2*y2; i++){
            for(int j=2*x1; j<=2*x2; j++){
                if(mat[i][j]==2) continue;
                mat[i][j]=2;
                if(i==2*y1 || i==2*y2 || j==2*x1 || j==2*x2){
                    mat[i][j]=1;
                }
            }
        }
        
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        Queue<int[]> que = new LinkedList<>();
        mat=new int[102][102];
        dist=new int[102][102];
        
        int[] dy = new int[]{-1,1,0,0};
        int[] dx = new int[]{0,0,-1,1};
        
        
        for(int[] r :rectangle){
            fill(r);
        }
        
        //BFS
        que.add(new int[]{2*characterY,2*characterX});
        
        while(!que.isEmpty()){
            int[] pos = que.poll();
            for(int i=0; i<4; i++){
                int ny = pos[0]+dy[i];
                int nx = pos[1]+dx[i];
                
                if(mat[ny][nx]==1 && dist[ny][nx]==0){
                    que.add(new int[]{ny,nx});
                    dist[ny][nx]=dist[pos[0]][pos[1]]+1;
                    
                    
                    if(nx==2*itemX && ny == 2*itemY){
                        
                        return dist[ny][nx]/2;
                    }
                }
            }
        }
        return dist[2*itemY][2*itemX]/2;
    }
}

---

🎸 기타

가. 처음 시작 지점도 2배가 된다.

 que.add(new int[]{2*characterY,2*characterX});

이 부분을 하지 않아서 오답이 나왔다.

---

🤔 느낀점

굉장히 어려웠던 문제이다. level3으로 갈 수록 어려운 문제가 많이 나오는 것 같다. 해당 문제는 경로 부분에서 굉장히 유용한 알고리즘이라고 생각된다.