[프로그래머스][Java] Lv.3 아이템 줍기

직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
• rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
  • 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
  • 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
  • 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
• charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• itemX, itemY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

---

고려사항

-  사각형을 겹친 다각형의 둘레 부분을 구하는 방법을 생각해야 한다.
    => 사각형의 둘레 부분은 1로 사각형 내부는 모두 2로 표시하여, 다각형의 둘레를 1로 표현했습니다.

-  ㄷ 형으로 파인 부분을 컴퓨터가 길로 인식해 ㅁ형으로 받아들여 탐색에 문제가 생기는 점을 고려해야 한다.

      => 모든 길이를 2배로 늘려 계산합니다. 길이 없는 부분을 확실히 구분하게 됩니다.

---

풀이 과정

1. 사각형을 겹친 다각형의 둘레를 구하기 위해 주어진 사각형을 차례로 돌면서,
   둘레에 해당하는 부분은 1로 사각형 내부에 해당하는 부분은 2로 나타냅니다.

   2. 사각형의 크기, character위치와 item 위치까지 모두 2배 시켜 DFS탐색을 진행합니다.

   3. 상하좌우 방향에 길이 있고 방문한 적이 없으면, dfs로 방문합니다.

   4. 도착지점에 도착하면 더 짧게 이동한 거리를 저장한 뒤 return 합니다.

   5. 최종적으로 dfs를 끝내고, 모든 크기를 2배로 늘렸기 때문에 이동한 최소거리도 원래대로 돌리기 위해
           /2를 해서 return 한다.

---

전체 코드

import java.util.*;
class Solution {
    static int[][] way = new int[102][102]; //좌표 값은 1이하 50이하 -> 2배로 늘림.
    					//[101][101]로 하면 런타입오류가 나니 조심!!
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    static int[] goal = new int[2];
    static boolean[][] visited; //방문했는지
    static int min=Integer.MAX_VALUE;
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        goal[0]=itemX*2;
        goal[1]=itemY*2;
        
        setWay(rectangle); //다각형 둘레 표시.
        //모든 크기의 두배
        characterX*=2;
        characterY*=2;
        
        for(int i=0;i<4;i++){
            if(way[characterX+dx[i]][characterY+dy[i]]==1){
                visited = new boolean[102][102];
                
                visited[characterX][characterY]=true;
                dfs(characterX+dx[i],characterY+dy[i],1); //이동과 동시에 dfs시작.
            }
        }
        
        return min/2;
    }
    private void dfs(int nowX, int nowY, int idx){
        //System.out.println("("+nowX+","+nowY+") "+idx);
        
        if(nowX==goal[0] && nowY==goal[1]){
            if(idx<min) min=idx;
            return;
        }
        //상하좌우에서 갈 수 있는 곳으로 가기.
        for(int i=0;i<4;i++){
            int newX = nowX+dx[i];
            int newY = nowY+dy[i];
            
            if(way[newX][newY]==1 && !visited[newX][newY]){
                
                visited[newX][newY]=true;
                dfs(newX,newY,idx+1);
                visited[newX][newY]=false;
            }
        }
    }
    //둘레:1, 사각형 내부:2
    private void setWay(int[][] rect){
        
        for(int i=0;i<rect.length;i++){
            for(int a=rect[i][0]*2;a<=rect[i][2]*2;a++){
                for(int b=rect[i][1]*2;b<=rect[i][3]*2;b++){
                    //오직 둘레(굵은 선)만 1.
                    if(a==rect[i][0]*2 || a==rect[i][2]*2 || b==rect[i][1]*2 || b==rect[i][3]*2){
                        if(way[a][b]==2) continue;
                        way[a][b]=1;
                    }//둘레가 아닌 부분은 2로 처리
                    else
                        way[a][b]=2;
                }
            }
        }
    }
}