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

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

프로그래머스

bfs를 사용하는 문제이다.

 

 

핵심 

문제에서 주어진 사각형들에 대해 겉 테두리만 돌아서 아이템 위치에 가장 빠르게 도착하는 횟수를 구해야 한다.

중요포인트는 map을 2배로 늘리는 것이다. 이유는 맵을 탐색할 때 선이 아닌 좌표 기준으로 하기 때문에 바로 연결되어

있는지 판단하기 쉬운 방법이 2배로 늘리는 것이기 때문이다. 

또한 내부 사각형과 테두리값을 구분해야 문제를 풀기 쉽다.

 

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int[][] map;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    static int answer;
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        map = new int[101][101];
        for (int[] r : rectangle)fill(2*r[0],2*r[1],2*r[2],2*r[3]);
        bfs(2*characterX,2*characterY,2*itemX,2*itemY);
        return answer;
    }

    public void fill(int x1, int y1, int x2, int y2){
        for (int i = x1; i<=x2; i++){
            for (int j = y1; j<=y2; j++){
                if (map[i][j] == 2)continue;
                map[i][j] = 2;
                if (i==x1||i==x2||j==y1||j==y2)map[i][j] = 1;
            }
        }
    }

    public void bfs(int startX, int startY, int itemX, int itemY){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startX,startY});
        int[][] cost = new int[101][101];
        cost[startX][startY] = 1;

        while (!q.isEmpty()){
            int[] move = q.poll();

            for (int i = 0; i < 4; i++){
                int moveX = move[0] + dx[i];
                int moveY = move[1] + dy[i];

                if (validation(moveX,moveY))continue;

                if (map[moveX][moveY] == 1 && cost[moveX][moveY] == 0){
                    cost[moveX][moveY] = cost[move[0]][move[1]]+1;
                    q.offer(new int[]{moveX, moveY});
                }
            }
        }
        answer = cost[itemX][itemY]/2;
    }

    public boolean validation(int x, int y){
        return (0>x || 0>y || x>100 ||y>100);
    }
}

해설

앞서 말한 대로 범위가 0~50이므로 2배를 하여 0~100으로 맵 사이즈를 늘려주었다.

이후 fill 메서드를 통해 내부와 테두리를 구분해 주었다. 

테두리의 경우 1, 내부의 경우 2로 표현하였다.

이제 bfs를 해야 하는데, 방문여부와 값을 저장할 cost를 만들어두었다.

만약 cost의 값이 아직 0이라면 아직 방문하지 않은 것이다.

이후 맵을 2배 하였으므로, answer값을 구할 때 값을 /2 해주어야 한다.