아이템 줍기 **

사용 알고리즘: bfs, 2배 늘리기...

사용 언어: java

 

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

//2배..
class Solution {
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    static int[][] map = new int[101][101];
        
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        for(int i=0; i<rectangle.length; i++) {
            int x1 = rectangle[i][0]*2;
            int y1 = rectangle[i][1]*2;
            int x2 = rectangle[i][2]*2;
            int y2 = rectangle[i][3]*2;
            draw(x1,y1,x2,y2);
        }
        
        // for(int i=0; i<101; i++) {
        //     System.out.println(Arrays.toString(map[i]));
        // }
        
        int[] character = new int[] {characterX*2, characterY*2};
        int[] item = new int[] {itemX*2, itemY*2};
        
        return bfs(character, item);
        
    }
    
    private static int bfs(int[] character, int[] item) {
        Queue<int[]> q = new ArrayDeque();
        q.offer(new int[] {character[0], character[1], 0});
        //0:x좌표 1;y좌표 2:움직인 수
        
        //갔던 곳 다시 가면 안 됨
        boolean[][] visited = new boolean[101][101];
        while(!q.isEmpty()) {
            int[] p = q.poll();
            if(p[0]==item[0] && p[1]==item[1]) {
                return p[2]/2; //맵을 2배로 늘렸으니까!!!!!!!
            }
            visited[p[0]][p[1]] = true;
            //
            for(int d=0; d<4; d++) {
                int x = dx[d] + p[0];
                int y = dy[d] + p[1];
                
                if(x>=0 && x<101 && y>=0 && y<101) {
                    if(!visited[x][y] && map[x][y] == 2) {
                        visited[x][y] = true;
                        q.offer(new int[] {x, y, p[2]+1});
                    }
                }
            }
        }
        return -1;
    }//
    
    private static void draw(int x1,int y1,int x2,int y2) {
        for(int i=x1; i<=x2; i++) {
            for(int j=y1; j<=y2; j++) {
                //가장자리는 2, 내부는 1
                //1. 가장자리가 먼저 칠해지고, 내부가 채워짐: 1로 바꾸기
                //2. 내부가 먼저 채워지고, 가장자리 칠하기: 1 그대로 있어야 함
                if(map[i][j] == 1) continue;
                map[i][j] = 1;
                if(i==x1||i==x2||j==y1||j==y2) {
                    map[i][j] = 2;
                }
            }
        }
    }
    //
}

 

1. 모서리 따라 움직이니까 2배 확장

    ( 그냥 하면, 한 칸 띄고 색칠되어 있는 것도 바로 이어진 거처럼 보이게 된다)

    => 따라서 받는 좌표도 *2

    => 따라서 움직이는 거리도 2배씩 되니까, 마지막엔 /2 

 

인사이트:

모서리 따라 움직일 떈 2배!