[프로그래머스,Java] Levle3: 위클리챌린지 11주차[아이템 줍기]

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

코딩테스트 연습 - 11주차

 

문제분석:

제 혼자힘으론 풀지 못했습니다.. 다른사람의 조언을 듣고 풀었죠

 

길찾기 문제입니다!

 

캐릭터 위치와, 아이템위치간의 최소거리를 구하는 문제

 

길찾기=완전탐색(DFS,BFS)이 딱 떠오릅니다.

 

 

하지만, 이 문제는 단순 길찾기알고리즘으론 못풉니다.  // 단순길찾기였으면 푸는사람도 많았겟지..

 

문제푸는 스킬, 사고력이 추가로 필요합니다. -> 전 이게 없었습니다..

 

왜? 풀지 못하는거지?  그림을 보고 설명해드리겠습니다.

 

저 빨간 부분이 문제입니다 ..

 

저희가 BFS를 가지고 문제를 푼다고하면, 4방향 (상,하,좌,우) 좌표를 하나씩 증가시켜

 

길을 탐색해 길따라 쭉가면 됩니다.

 

하지만.. 사람과는 달리 컴퓨터는 좌표로 길을 탐색합니다.  둘이 비교를 해보죠

 

 

컴퓨터야...ㅠㅠㅠ

 

사람이 그림을 보면  아니.. 당연히 돌아가야지..  인데,

 

컴퓨터는 좌표로 길을 판단하기때문에, 길을 두갈래로 타버립니다.   

 

이 문제를 해결하는 방법은 그림을 2배 확대시키면 됩니다.

 

그림을 2배 확대시키면, 좌표마다 사이사이에, 빈칸이 나타나겠죠? 

그럼 컴퓨터도 길을 탐색할때 지나치지않고 제대로 (우회)돌아가면서 탐색합니다.

 

 

제대로 문제 풀 전략도 갖춰졌으니 풀어봅시다!

 

1. 좌표를 모두 2배 늘립니다.

2. 길을 그릴 boolean[][] map도 2배로 늘립니다.  제한사항이 50이 최대니, 51*2  넉넉하게 크기103을 잡았다.

3. 테두리 포함해서, 직사각형을 map[][]에다 True를 할당

4. 테두리 제외해서, 직사각형을 map[][] 에다 False를 할당 -->이렇게하면 테두리만 남은 True 길이 형성

5. BFS 탐색

6.  캐릭터위치~ 아이템거리를 측정한 result값 하나 저장.  (이 길이가 최소, 최대인지 모르니깐)

7.  캐릭터위치~ 캐릭터 위치까지(1바퀴)를 측정한 result값 하나더 저장 (전체 테두리 길이)

8. Math.min(캐릭터위치~아이템거리, 전체 테두리길이 - 캐릭터위치~아이템거리)를 출력하자. 

 

 

문제풀이:

import java.util.*;
class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        
        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];
        int ted=0;
        
        for(int[] data:rectangle){
            //1.테두리 포함해서 직사각형 모두 true채우기
            for(int i=data[1]*2;i<=data[3]*2;i++){
              for(int j=data[0]*2;j<=data[2]*2;j++){
                    map[i][j]=true;
                  
              }  
            }
        }
        
        for(int[] data:rectangle){
            //2.테두리 제외해서 직사각형 내부 모두 false채우기
            for(int i=data[1]*2+1;i<data[3]*2;i++){
              for(int j=data[0]*2+1;j<data[2]*2;j++){
                    map[i][j]=false;
              }  
            }
        }
    
        //bfs 탐색
        Stack<Player> stack = new Stack<>();
        
        // 시작점 설정
        Player p = new Player(start_x,start_y);
        stack.add(p);
        
        List<Integer> result =new ArrayList<>();
        int cnt=0;
        
        while(true){       
            if(stack.isEmpty()){
                result.add(cnt);
                break;
            }
            Player temp=stack.pop();
            int x=temp.x;
            int y=temp.y; 
           
            //도착하면 갯수 저장
            if(x==end_x&&y==end_y){
                result.add(cnt);         
            }
            
            //지났으면 지난자리 false               
            map[y][x]=false;
            
            if(map[y+1][x]==true) stack.add(new Player(x,y+1));
            if(map[y][x+1]==true) stack.add(new Player(x+1,y));
            if(map[y-1][x]==true) stack.add(new Player(x,y-1));
            if(map[y][x-1]==true) stack.add(new Player(x-1,y));
            
            cnt++;
            
        }
        
        answer=Math.min(result.get(0)/2,result.get(1)/2-result.get(0)/2);      
        return answer;
    }
    
    class Player{
        int x;
        int y;
        
        public Player(int x, int y){
            this.x=x;
            this.y=y;   
        }
    }
}