[JAVA] [BFS] Pro 아이템 줍기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=java 

프로그래머스

풀이

1. 좌표를 2배로 늘린다. (3,5) -> (3,6) 원래는 갈 수 없는 길인데 좌표이동으로는 갈 수 있는것 처럼 보이기 때문이다.

2. 테두리 만을 남기기 위해 사각형의 전체 영역을 true로 채운 후, 내부를 false로 다시 채운다

3. bfs를 통해 최단경로 탐색한다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        
        int[] dx={-1,1,0,0};
        int[] dy={0,0,-1,1};
        
        int start_x=characterX*2;
        int start_y=characterY*2;
        int end_x=itemX*2;
        int end_y=itemY*2;
        
        boolean[][] map= new boolean[103][103];
        
        for(int[] data:rectangle){
            //1.테두리 포함해서 직사각형 모두 true채우기
            for(int i=data[0]*2;i<=data[2]*2;i++){
              for(int j=data[1]*2;j<=data[3]*2;j++){
                    map[i][j]=true;
              }  
            }
        }
        
        for(int[] data:rectangle){
            //2.테두리 제외해서 직사각형 내부 모두 false채우기
            for(int i=data[0]*2+1;i<data[2]*2;i++){
              for(int j=data[1]*2+1;j<data[3]*2;j++){
                    map[i][j]=false;
              }  
            }
        }
        
        
        Queue<Point> q= new LinkedList<>();
        int[][] visited= new int[103][103];
        q.add(new Point(start_x, start_y));
        visited[start_x][start_y]=1;
        while(!q.isEmpty()){
            Point p = q.poll();
            
            if (p.x==end_x && p.y==end_y){
                break;
            }
            for(int i=0; i<4; i++){
                int nx=p.x+dx[i];
                int ny=p.y+dy[i];
                if (nx>0 && nx<103 && ny>0 && ny<103){
                    if(visited[nx][ny]==0 && map[nx][ny]==true){
                        q.add(new Point(nx,ny));
                        visited[nx][ny]=visited[p.x][p.y]+1;
                    }
                }
            }
        }

        answer=visited[end_x][end_y]/2;
        
        
        return answer;
    }
    class Point{
        int x;
        int y;
        
        public Point(int x, int y){
            this.x=x;
            this.y=y;   
        }
    }
}