아이템 줍기

---

풀이 방법

문제를 풀기 위해 테두리를 먼저 구해주었다. 하지만 그냥 테두리를 구하게 되면 ㄷ으로 꺽이는 경로는 컴퓨터 상 경로를 찾기 힘들어서 지형자체를 2배 해서 풀어주었다. 2배 해서 테두리를 구해준 뒤 dfs를 통해 최단 경로를 구해주었다. 

아이템 위치를 찾게 되면 아이템은 visited를 다시 false 처리 해줘서 다시 탐색할 수 있도록 하였다.

 

내 코드

import java.util.*;

class Solution {
    static int[][] array;
    static int[][] way = {{1,0}, {-1,0}, {0,1}, {0,-1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    static boolean[][] visited;
    static int answer = Integer.MAX_VALUE;
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {

        array = new int[102][102];
        visited = new boolean[102][102];
        
        for(int k = 0; k < rectangle.length; k++){
            for(int i = 2 * rectangle[k][0]; i <= 2 * rectangle[k][2]; i++){
                for(int j = 2 * rectangle[k][1]; j <= 2 * rectangle[k][3]; j++){
                    array[i][j] = 1;
                }
            }
        }
        
        for(int k = 0; k < rectangle.length; k++){
            for(int i = 2 * rectangle[k][0] + 1; i < 2 * rectangle[k][2]; i++){
                for(int j = 2 * rectangle[k][1] + 1; j < 2 * rectangle[k][3]; j++){
                    array[i][j] = 0;
                }
            }
        }
            
        dfs(characterX * 2, characterY * 2, 0, itemX * 2, itemY * 2);
        
        answer /= 2;
        
        return answer;
    }

    static void dfs(int x, int y, int len, int itemX, int itemY){
        visited[x][y] = true;

        if(x == itemX && y == itemY){
            answer = Math.min(answer, len);
            visited[x][y] = false;
            return;
        }
        
        for(int i = 0; i < 4; i++){
            if(array[x + way[i][0]][y + way[i][1]] == 1 && !visited[x + way[i][0]][y + way[i][1]]){
                dfs(x + way[i][0], y + way[i][1], len + 1, itemX, itemY);   
            }
        }
    }   
}