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

문제

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

코딩테스트 연습 - 11주차

풀이

좌표평면 위에 여러 사각형이 겹쳐지는데 , 이들을 겉 돌면서 최종목표까지 탐색하는 방법이다.
사각형이 그려지는 면적을 allowed로 체크해주고
겉 둘레만 돌기위해 visit 배열로 사각형 내부만 true 로 준다. (외부는 false 그대로 놔둠)

여기서 중요한데 , 만약 이 상태에서 그냥 탐색을 해버리면 문제의 구간이 발생한다.

(3,5) 구간. 여기가 왜 문제냐면 , 보통 좌표평면을 그래프 탐색을 할 땐 
for 문으로 상하좌우 갈수있는 좌표를 탐색해서 !visit 이거나 갈 수 있는곳 일때만 탐색을 하기 때문.
여기선 둘레를 돌아야 하는데 , (3,5) 에서 (3,6)으로 바로 뛰어 넘는것을 예외 처리 할 수가 없음.
stack으로 백트랙킹도 해보고 예외 처리를 만들어도 또 다른 예외가 계속 발생했다..

그래서 주어진 면적을 2배로 줘서 상하좌우를 살폈을 때 , allowed 를 만족하지 못하므로 통과불가하게 만듬
즉 , 탐색은 한칸씩 하되 주어진 모든 좌표나 면적을 2배로 늘림으로써 해결됨.
return 되는 정답은 나온 카운트값/2 해주면 끝.

 

 

import java.util.*;
import java.io.*;
 
class Solution {
 
    static boolean[][] allowed = new boolean[102][102], visit = new boolean[102][102];
    static int[] dx={0,0,1,-1},dy={1,-1,0,0};
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        initMap(rectangle);
        LinkedList<int[]> q = new LinkedList<>();
        q.add(new int[]{characterX*2,characterY*2,0}); visit[characterY*2][characterX*2]=true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[1]==itemY*2 && cur[0]==itemX*2) return cur[2]/2;
            for(int i=0;i<4;i++){
                int nextX = cur[0]+dx[i];
                int nextY = cur[1]+dy[i];
                if(!visit[nextY][nextX] && allowed[nextY][nextX]){
                    q.add(new int[]{nextX,nextY,cur[2]+1});
                    visit[nextY][nextX]=true;
                }
            }
        }
        return 0;
    }
 
    private void initMap(int[][] rectangle) {
        for (int[] rec : rectangle) {
            for(int i=rec[0]*2;i<=rec[2]*2;i++){
                for(int j=rec[1]*2;j<=rec[3]*2;j++){
                    allowed[j][i]=true;
                    if(i>rec[0]*2 && i<rec[2]*2 && j>rec[1]*2 && j<rec[3]*2) visit[j][i]=true;
                }
            }
        }
    }
 
}