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

문제 설명

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

문제 풀이

• BFS를 이용하여 풀이하였다.
• 문제의 풀이 순서는 간단하다

  1. 격자를 만들고 직사각형에 해당하는 칸을 1로 치환해준다.
  2. 시작점에서 BFS를 수행하되 다음칸에 8방향 확인 후 빈공간이 있으면 진행시킨다.

• 위와 같이 진행했을때 큰 예외 케이스가 존재한다.

0007611  문제에 주어진 그대로 좌표에 직사각형을 채웠을 경우       0009871
0000511  왼쪽의 예시처럼 2~7으로 진행하는 것으로 생각할 수 있지만  0000561
0003411  사실 오른쪽처럼 2~9로 진행해야하는 케이스가 존재한다.    0003411
0002111												  0002111	

• 위와 같은 케이스를 고려하기 위해 모든 좌표값에 * 2를 하여 축적을 늘려서 BFS를 진행하고
  결과에 나누기 2를 해주어야 한다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public boolean[][] map = new boolean[101][101];
    public boolean[][] chk = new boolean[101][101];
    public int[] dx = {0,0,1,-1};
    public int[] dy = {1,-1,0,0};
    public int[] dx2 = {-1, -1, 0, 1, 1, 1, 0, -1};
    public int[] dy2 = {0, 1, 1, 1, 0, -1, -1, -1};

    public class Point {
        int x, y, d;

        public Point(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        //맵 그리기
        for (int i = 0; i < rectangle.length; i++) {
            int x1 = rectangle[i][0] * 2;
            int y1 = rectangle[i][1] * 2;
            int x2 = rectangle[i][2] * 2;
            int y2 = rectangle[i][3] * 2;
            for (int x = x1; x <= x2; x++)
                for (int y = y1; y <= y2; y++)
                    map[x][y] = true;
        }

        //BFS 시작
        Queue<Point> q = new ArrayDeque<>();
        chk[characterX * 2][characterY * 2] = true;
        q.add(new Point(characterX * 2, characterY * 2, 0));

        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.x == itemX * 2 && cur.y == itemY * 2)
                return cur.d / 2;
            for (int d = 0; d < 4; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (X < 0 || Y < 0 || X > 100 || Y > 100) continue;
                if (chk[X][Y] || !map[X][Y]) continue;
                //다음 좌표에서 4방향 중 빈공간이 있는지 확인 -> 빈공간 있으면 false
                boolean flag = true;
                for (int dir = 0; dir < 8; dir++) {
                    int nextX = X + dx2[dir];
                    int nextY = Y + dy2[dir];
                    if (nextX < 0 || nextY < 0 || nextX > 100 || nextY > 100 || !map[nextX][nextY]) {
                        flag = false;
                        break;
                    }
                }
                //빈공간 없지만 특정 사각형의 선분이면 넣어줌
                if (flag) continue;
                chk[X][Y] = true;
                q.add(new Point(X, Y, cur.d+1));
            }
        }
        return -1;
    }
}