[Programmers] 아이템 줍기

난이도 : Level 3

문제링크

• 캐릭터가 아이템을 줍기 위해 이동함
• 캐릭터는 지형의 가장 바깥쪽 테두리를 따라 이동함
• 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 리턴하라

 

• 각 지형은 직사각형으로 지형들끼리 서로 겹쳐져있다
  • 서로 다른 두 지형들이 x축 또는 y축 좌표가 같은 경우는 없음
  • 두개 이상 분리된 경우도 없음
  • 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우도 없음

 

해설

• 이동할 수 있는 경계 좌표만 이동할 수 있도록 좌표를 가진 2차원 boolean 배열에 경계좌표를 체크함
• 이동할 수 없는 사각형 내의 좌표들을 캐릭터가 다음 턴에 내부 좌표에 이동하지 못하도록 방문처리함

import java.util.*;

class Solution {
    int m, n;
    boolean[][] visited, available;
    int[] dy, dx;
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        m = 102;
        n = 102;
        
        visited = new boolean[m+1][n+1];
        init(rectangle);
        dy = new int[] {0, 0, 1, -1};
        dx = new int[] {1, -1, 0, 0};
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{characterY*2, characterX*2, 1});
        visited[characterY*2][characterX*2] = true;
        
        while (!queue.isEmpty()) {
            int[] peek = queue.poll();
            int cy = peek[0];
            int cx = peek[1];
            int ct = peek[2];        
            
            if (cy == itemY*2 && cx == itemX*2) {
                return ct/2;
            }
            
            for (int i = 0; i < 4; i++) {
                int ny = cy + dy[i];
                int nx = cx + dx[i];
                int nt = ct + 1;
                
                if (validate(ny, nx)) {
                    visited[ny][nx] = true;
                    queue.offer(new int[]{ny, nx, nt});
                }
            }
        }
        
        return 0;        
    }
    
    private void init(int[][] rect) {        
        this.available = new boolean[m][n];
        for (int[] rec : rect) {
            for (int r = rec[1]*2; r <= rec[3]*2; r++) {
                for (int c = rec[0]*2; c <= rec[2]*2; c++) {                               
                    this.available[r][c] = true;
                    if (r > rec[1]*2 && r < rec[3]*2 && c > rec[0]*2 && c < rec[2]*2) {
                        this.visited[r][c] = true;   
                    }
                }
            }
        }                               
    }
    
    private boolean validate(int ny, int nx) {
        if (ny < 0 || ny > m || nx < 0 || nx > n) {
            return false;           
        }
        
        if (!available[ny][nx]) {
            return false;
        }    
        
        if (visited[ny][nx]) {
            return false;
        }    
        
        return true;
    }
}

(출처 : kimkata's Devlog)