아이템 줍기 - JAVA, BFS

 

 

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

프로그래머스

 

 

코드 & 풀이

 

import java.util.*;

class Solution {
    static final int SIZE = 102;
    static int[][] board = new int[SIZE][SIZE];
    static boolean[][] visited = new boolean[SIZE][SIZE];
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        for (int[] rec : rectangle) {
            int x1 = rec[0] * 2, y1 = rec[1] * 2;
            int x2 = rec[2] * 2, y2 = rec[3] * 2;
            for (int i = x1; i <= x2; i++) {
                for (int j = y1; j <= y2; j++) {
                    board[i][j] = 1;
                }
            }
        }

        
        for (int[] rec : rectangle) {
            int x1 = rec[0] * 2, y1 = rec[1] * 2;
            int x2 = rec[2] * 2, y2 = rec[3] * 2;
            for (int i = x1 + 1; i < x2; i++) {
                for (int j = y1 + 1; j < y2; j++) {
                    board[i][j] = 0;
                }
            }
        }

        return bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2) / 2;
    }

    private int bfs(int startX, int startY, int endX, int endY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY, 0});
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], dist = cur[2];

            if (x == endX && y == endY) {
                return dist;
            }

            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if (nx >= 0 && ny >= 0 && nx < SIZE && ny < SIZE) {
                    if (board[nx][ny] == 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.add(new int[]{nx, ny, dist + 1});
                    }
                }
            }
        }

        return -1; // 도달 불가능한 경우
    }
}

 

좌표를 2배로 해서 진행 → 일단 네모 그림 → 안에 비우기 → BFS 탐색 → 결과 나누기 2함

 

왜 좌표를 2배로 키우냐?

 

우리는 외곽을 따라서 움직여야 함.

 

문제는 꼭지점 → 이동을 2배로 해야하는데, 원본으로는 이걸 못 함.

 

그래서 2배로 늘린거임.

 

 

 

 

 

다음에 또 봐요