프로그래머스(아이템 줍기)

첫 시도

• 테두리를 따라서 이동하는 것이 핵심이라고 생각했음
• 맵을 만들고 입력받은 사각형의 좌표대로 사각형을 만들어줌(1로 채우기)
• 배열로 만든 맵의 최단거리를 찾는 것은 bfs가 최적이므로 bfs 사용 -> 이 문제같은 경우에는 dfs를 사용해도 무방할 것 같음
• 이동조건으로는 주변에 1이 있어야 bfs큐에 add해주려고 함 -> 사각형의 모서리에 도달하면 주변에 1이 없어 add되지 못함 -> 구현 실패

해결

• 사각형의 좌표를 입력받아 맵을 만들고 사각형의 내부를 0으로 채움 -> 테두리만 남게되어 bfs로 쉽게 이동 가능
• 이때, 기존 사이즈대로 맵을 만들면 테두리끼리 닿게 되어 원하는대로 탐색 할 수 없음 -> 전체적인 사이즈를 x2 하여 빈 공간 구현, 원하는대로 탐색 가능

import java.util.*;

class Solution {
    static int min;
    static int[] dr = {0,-1,0,1};
    static int[] dc = {-1,0,1,0};
    static int[][] map;
    static boolean[][] visited;


    public static int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        min = Integer.MAX_VALUE;
        map = new int[102][102];
        visited = new boolean[102][102];
        buildMap(rectangle);
        map[itemY*2][itemX*2] = -1;
        bfs(characterX*2,characterY*2,itemX*2,itemY*2);
        answer = min/2;

        return answer;

    }

    static void bfs(int cX, int cY, int iX, int iY){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {cY,cX,0});
        visited[cY][cX] = true;
        while(!q.isEmpty()){
            int[] temp = q.poll();
            int r = temp[0];
            int c = temp[1];
            int count = temp[2];

            if(map[r][c] == -1){
                min = Math.min(min,count);
            }

            for(int i = 0; i<4; i++){
                int nr = r+dr[i];
                int nc = c+dc[i];
                if(nr < 0 || nr >= 102 || nc < 0 || nc >= 102) continue; // 범위 밖이면 제
                if(visited[nr][nc] || map[nr][nc] == 0) continue; // 방문했거나 길이 아니면 제외
                q.add(new int[] {nr,nc,count+1});
                visited[nr][nc] = true;
            }
        }
    }

    static void buildMap(int[][] rectangle) {

        for(int t = 0; t< rectangle.length; t++){ // 직사각형 채우기
            int c1 = rectangle[t][0] *2;
            int r1 = rectangle[t][1] *2;
            int c2 = rectangle[t][2] *2;
            int r2 = rectangle[t][3] *2;
            for(int i = r1; i<=r2; i++){
                for(int j = c1; j<=c2; j++){
                    map[i][j] = 1;
                }
            }
        }
        for (int t = 0; t < rectangle.length; t++) {
            int c1 = rectangle[t][0] *2+1;
            int r1 = rectangle[t][1] *2+1;
            int c2 = rectangle[t][2] *2-1;
            int r2 = rectangle[t][3] *2-1;
            for(int i = r1; i<=r2; i++){
                for(int j = c1; j<=c2; j++){
                    map[i][j] = 0;
                }
            }
        }
    }
}

참고

• https://taehoung0102.tistory.com/95