[pro] 프로그래머스 level3 87694 아이템 줍기 - BFS

[문제]

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

프로그래머스

 

[풀이]

문제를 푸는 핵심은 좌표를 2배로 확장하는 것이다.

테두리로만 이동하도록 하기 위해서, 먼저 테두리를 포함한 모든 사각형을 1로 채운 후, 테두리를 제외한 안쪽을 0으로 다시 바꿔 채워주었다.

 

  

이때 bfs를 돌리려고 하면 컴퓨터가 좌표로 길을 판단하기 때문에 테두리를 구분하지 못하는 문제가 발생한다.

예를 들어, 위 그림에서 (3, 5), (4, 5), (3, 6), (4, 6)은 모두 테두리로 표시되어있을 것이다. 그럼, (3, 5)에서 이동하기 위해 상하좌우 탐색을 하면 (3, 6), (4, 5) 모두 테두리이기 때문에 이동할 수 있다고 여길 것이다. 하지만 실제로는 (3, 5)에서 (3, 6)으로 이동할 수 없다. 

이를 구분해주기 위해서 좌표를 2배로 늘리면 (6, 10), (8, 10), (6, 12), (8, 12)가 된다. (6,10)과 (6, 12) 사이에 (6, 11)이 생기고 이는 테두리가 아니라는 표시가 되어있기 때문에 쉽게 테두리로만 이동하도록 만들 수 있다.  

 

[코드]

 

import java.util.*;

class Solution {
    int[][] map;
    int ans;
    boolean[][] visited;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        //캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return
        
        map = new int[102][102];
        
        //테두리 표시하기
        for(int[] r:rectangle){
            for(int x=r[0]*2; x<=r[2]*2; x++){
                for(int y=r[1]*2; y<=r[3]*2; y++){
                    map[x][y] = 1;
                }
            }
        }
        
        for(int[] r:rectangle){
            for(int x=r[0]*2+1; x<=r[2]*2-1; x++){
                for(int y=r[1]*2+1; y<=r[3]*2-1; y++){
                    map[x][y] = 0;
                }
            }
        }
        
        bfs(2*characterX, 2*characterY, 2*itemX, 2*itemY);
        
        return ans;
    }
    
    public void bfs(int cX, int cY, int iX, int iY){
        visited = new boolean[102][102];
        Queue<Point> q = new LinkedList<>();
        visited[cX][cY] = true;
        q.add(new Point(cX, cY, 0));
        
        while(!q.isEmpty()){
            Point p = q.poll();
            
            if(p.x==iX && p.y==iY){
                ans = p.distance/2;
                return;
            }
            
            for(int i=0; i<4; i++){
                int nx = dx[i] + p.x;
                int ny = dy[i] + p.y;
                
                //테두리로만 이동
                if(!visited[nx][ny] && map[nx][ny]==1){
                    visited[nx][ny] = true;
                    q.add(new Point(nx, ny, p.distance+1));
                }
                
            }
        }
    }
    
    static class Point{
        int x, y, distance;
        Point(int x, int y, int distance){
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
}