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

정보

1. 소요시간 : 20분.
2. 문제 사이트 : 프로그래머스
3. 문제 수준 : 레벨 3
4. 문제 유형 : BFS
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87694
8. 푼 날짜 : 2023.03.06

1. 사용한 자료구조 & 알고리즘

BFS 를 사용했다. 시작 위치와 종료의 위치를 알고있으니 BFS를하면서 시작위치에서 종료위치를 가는 count 를 세어주면 된다.

2. 풀이과정

우선 가장 신경써줘야 할 부분이 2개가 있다. BFS를 하는 것을 이해했다면 이제 다음은 맵의 크기를 왜 2배로 늘리는 것과, 어떻게 테두리만 필터링할 수 있는지에 대한 이해가 필요하다.
먼저 맵의 크기를 2배로 늘리는 이유는 BFS 를 하면서 테두리를 따라가는 중에 내 테두리가 아닌 옆의 테두리로 셀 수 도있기 때문이다. 테스트케이스 1번을 보면서 맵을 그려본다면 이해할 수 있을 것이다.
그리고 테두리만 필터링하는 것은 맵의 2중 for문으로 y또는 x의 시작좌표, 혹은 y또는 x의 끝좌표 일 때만 2로 칠해주고, 그렇지 않은 것은 1로 칠해줌으로써 테두리만 고를 수 있다.

1. rectangle 배열에서 테두리의 y,x 좌표를 각각 뽑아내고, 그 크기를 2배로 늘려서 칠해준다.
2. BFS 를 시작해주는데 맵의 크기를 2배로 늘렸고, 좌표도 그에따라 2배가 되므로 BFS의 시작좌표, 그리고 찾고있는 아이템의 좌표도 2배로 늘려준다. ( 이것을 해주지 않아서 5분 정도 헤맸다... )
3. 그 후 BFS 를 해주면서 내 [상, 하, 좌, 우 ] 를 보고, itemY, itemX 를 찾는다. 찾고 나면 이제 그 좌표는 2배가 되어 있을 것이므로 count를 2로 나눈 값을 return 한다.

깨알 tip. 이 문제는 map의 상태가 1 혹은 2이므로 map을 int 로 해주지 않고 char 로 해주면 메모리의 측면에서 더 이점이 있다.

3. 소스코드

import java.util.*;
class Solution {
  
    static char map[][]=new char[101][101];
    public int solution(int[][] rectangle, int X, int Y, int itemX, int itemY) {
        for(int i=0;i<rectangle.length;i++){
            int y1=rectangle[i][1];
            int x1=rectangle[i][0];
            int y2=rectangle[i][3];
            int x2=rectangle[i][2];  
            draw(y1*2,x1*2,y2*2,x2*2);
        }
        
        return bfs(Y*2,X*2,itemY*2,itemX*2);
        
        
    
    }
    public static int bfs(int Y,int X,int findY,int findX){
        int yy[]={-1,1,0,0};
        int xx[]={0,0,-1,1};
        Queue<Integer[]> queue=new LinkedList<>();
        queue.add(new Integer[]{Y,X,0});
        boolean visited[][]=new boolean[101][101];
        while(!queue.isEmpty()){
            Integer temp[]=queue.poll();
            int prevY=temp[0];
            int prevX=temp[1];
            int count=temp[2];
            if(prevY==findY&&prevX==findX)
                return count/2;
            for(int i=0;i<4;i++){
                int nextY=prevY+yy[i];
                int nextX=prevX+xx[i];
                if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length)
                    continue;
                if(visited[nextY][nextX]==true||map[nextY][nextX]!='2')
                    continue;
                
                visited[nextY][nextX]=true;
                queue.add(new Integer[]{nextY,nextX,count+1});
              
            }
        }
        
        return 0;
    }
    public static void draw(int y1,int x1,int y2,int x2){
        
        for(int i=y1;i<=y2;i++){
            for(int j=x1;j<=x2;j++){
            	if(map[i][j]=='1') continue;
                map[i][j]='1';
                if(i==y1||i==y2||j==x1||j==x2)
                    map[i][j]='2';
            }
        }
        
    }
}

4. 회고

맵을 왜 2배로 늘려주는지와 테두리를 필터링 하는 것에 대한 이해가 있고, BFS를 할 줄 안다면 풀 수 있다. 나는 이전에 BFS 만 할 줄 알았고 , 왜 맵을 2배로 늘리는지에 대한 이해와 테두리를 필터링 하는 법을 몰랐기에 다른 사람의 풀이를 참고했었다. 그렇게 1주일 정도가 지난 후 혼자 다시 풀어봤는데도 그렇게 오래 걸리지 않게 풀었으므로 이제 이 문제와 비슷한 유형의 문제가 나온다고 해도 맞출 수 있을 것 같은 자신감이 든다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212