BFS+가중치 = Dequeue

문제 : https://www.acmicpc.net/problem/1584

🚨오늘의 학습🚨

🎯 가중치 있는 BFS 🎯

가중치❌(일정) 경우 → 큐
💡가중치👌🏻 경우 → Deque/Dijkstra💡
🔸 가중치를 고려하지 않으면 더 나은 경우의 경로를 놓치게 됨

[예제문제]

1. 가중치가 일정한 경우의 최소 비용 ➡️ 방문여부 확인(재방문X) https://school.programmers.co.kr/learn/courses/30/lessons/1844
2. 가중치가 다른 경우의 최소 비용 ➡️ 다른 경로에서 방문하는 경우가 더 최소일수 있기때문에 재방문O
   https://www.acmicpc.net/problem/1584

---

• Dequeue

public class Main {

    static final int INF = Integer.MAX_VALUE;
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    static int[][] grid = new int[501][501];
    static int[][] cost = new int[501][501];


    public static void bfs() {
            Deque<int[]> dq = new LinkedList<>();
            dq.offer(new int[]{0, 0});
            cost[0][0] = 0;

            while (!dq.isEmpty()) {
                int[] now = dq.pollFirst();
                int cx = now[0], cy = now[1];

                for (int[] dir : dirs) {
                    int nx = cx + dir[0], ny = cy + dir[1];

                    if (!inRange(nx, ny) || grid[nx][ny] == 2) {
                        continue;
                    }

                    int newCost = cost[cx][cy] + (grid[nx][ny] == 1 ? 1 : 0);
                    if (newCost < cost[nx][ny]) {
                        // 🎯 더 적은 비용으로 Update
                        cost[nx][ny] = newCost;
                        if (grid[nx][ny] == 1) {
                            // 가중치를 반영한 큐 삽입
                            // 🔸가중치 높은 위험구역의 경우 뒤에서 삽입
                            // 우선순위 큐처럼 삽입
                            dq.offerLast(new int[]{nx, ny});
                        } else {
                            // 🔸 가중치 낮은 안전구역의 경우 앞에서 삽입
                            // 우선순위 큐처럼 삽입
                            dq.offerFirst(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // grid 초기화
        for (int i = 0; i < 501; i++) {
            Arrays.fill(grid[i], 0);
            // 🎯 방문 여부를 확인할 필요가 없기때문에 
            // 비용의 최소값을 구해야 하므로 
            // 최대값으로 초기화
            Arrays.fill(cost[i], INF);
        }

        // 위험 구역 입력
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            for (int x = Math.min(x1, x2); x <= Math.max(x1, x2); x++) {
                for (int y = Math.min(y1, y2); y <= Math.max(y1, y2); y++) {
                    grid[x][y] = Math.max(grid[x][y], 1); // 위험
                }
            }
        }

        // 죽음 구역 입력
        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            for (int x = Math.min(x1, x2); x <= Math.max(x1, x2); x++) {
                for (int y = Math.min(y1, y2); y <= Math.max(y1, y2); y++) {
                    grid[x][y] = 2; // 죽음
                }
            }
        }

        // 시작점 (0, 0)과 끝점 (500, 500) 처리
        if (grid[500][500] == 2) {
            System.out.println(-1);
            return;
        }

        // BFS 수행
        bfs();

        // 결과 출력
        int result = cost[500][500];
        System.out.println(result == INF ? -1 : result);
    }

    

    public static boolean inRange(int x, int y) {
        return x >= 0 && y >= 0 && x <= 500 && y <= 500;
    }
}