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

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

import java.util.*;
import java.io.*;

class Solution {

    static boolean[][] map;
    static Queue<Point> queue;
    static boolean[][] visited;
    static int ans;
    static int sX, sY, iX, iY;
    
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static class Point{
        int x;
        int y;
        int cnt;
        
        Point(int x, int y, int cnt){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    static void fill(int x1, int y1, int x2, int y2){
        for(int i=x1;i<=x2;i++){
            map[i][y1] = true;
            map[i][y2] = true;
        }
        for(int i=y1;i<=y2;i++){
            map[x1][i] = true;
            map[x2][i] = true;
        }
    }
    
    static void getLine(int x1, int y1, int x2, int y2){
        for(int i=x1+1;i<x2;i++){
            for(int j=y1+1;j<y2;j++){
                map[i][j]=false;
            }
        }
    }
    
    static void getAnswer(int x, int y, int cnt){
        queue = new LinkedList<>();
        queue.add(new Point(x, y, cnt));
        visited[x][y] = true;
        
        while(!queue.isEmpty()){
            Point tmp = queue.poll();
            
            if(tmp.x==iX && tmp.y==iY){
                ans = Math.min(tmp.cnt/2,ans);
            }
            for(int d=0;d<4;d++){
                int nx = tmp.x + dx[d];
                int ny = tmp.y + dy[d];
                if(nx<0||nx>=101||ny<0||ny>=101) continue;
                if(!visited[nx][ny]&&map[nx][ny]){
                    queue.add(new Point(nx,ny,tmp.cnt+1));
                    visited[tmp.x][tmp.y]=true;
                }
            }     
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        map = new boolean[101][101];
        visited = new boolean[101][101];
        sX = characterX *2;
        sY = characterY *2;
        iX = itemX *2;
        iY = itemY *2;
        
        ans = Integer.MAX_VALUE;
        
        
        for(int i=0;i<rectangle.length;i++) {
            int lx = rectangle[i][0];
            int ly = rectangle[i][1];
            int rx = rectangle[i][2];
            int ry = rectangle[i][3];
            
            fill(2*lx, 2*ly, 2*rx, 2*ry);
        }
        
        for(int i=0;i<rectangle.length;i++) {
            int lx = rectangle[i][0];
            int ly = rectangle[i][1];
            int rx = rectangle[i][2];
            int ry = rectangle[i][3];
            
            getLine(2*lx, 2*ly, 2*rx, 2*ry);
        }
        
        getAnswer(sX,sY,0);

        return ans;
    }
}

오랜만에 프로그래머스로 문제를 푸니 자동완성이 안되어서 확실히 ,, 불편했다.

생각을 해보아도 bfs를 이용하는 것, 사각형을 그리는 것은 알겠는데 테두리만 처리하는 법을 모르겠어서 검색을 했다 ㅜㅜ..

검색을 했을 때 처음에는 map의 크기, x,y좌표들의 크기를 2배 하는 것을 이해하지 못했는데 이해를 하고 나니 크게 어려운 문제는 아니었다.

위 그림 같은 경우에 x=3, x=4일때 테두리를 따라 갈 수 없는 문제(초록 동그라미 부분 처리 불가)를 해결하기 위해 두배를 하는 것이다.

또, 테두리만 처리하는 법이 생각보다 복잡하거나 어려운게 아니었다. 문제만 보고 겁먹지 말아야겠다는 생각을 했다. 

 

1. 사각형 좌표 두배 해서 map에 모든 사각형 표시하기

2. 사각형 내부에 있는 테두리는 지우기

3. bfs로 아이템까지의 최단거리 구하기 (2배 해줬으므로 2로 나눠주어야함)