[백준 1584] 게임 - JAVA

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

 

다익스트라 or 0-1 BFS 문제

 

다익스트라로 풂

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

  static class Node {

    int r, c, d;

    Node(int r, int c, int d) {
      this.r = r;
      this.c = c;
      this.d = d;
    }
  }

  public static void main(String[] args) throws IOException {

    int[][] m = new int[501][501];
    int[] dr = {0, 0, -1, 1};
    int[] dc = {-1, 1, 0, 0};

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    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());

      int sx = Math.min(x1, x2);
      int ex = Math.max(x1, x2);
      int sy = Math.min(y1, y2);
      int ey = Math.max(y1, y2);

      for (int x = sx; x <= ex; x++) {
        for (int y = sy; y <= ey; y++) {
          m[y][x] = 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());

      int sx = Math.min(x1, x2);
      int ex = Math.max(x1, x2);
      int sy = Math.min(y1, y2);
      int ey = Math.max(y1, y2);

      for (int x = sx; x <= ex; x++) {
        for (int y = sy; y <= ey; y++) {
          m[y][x] = 2;
        }
      }
    }

    int INF = 501 * 501;

    PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparing(n -> n.d));
    q.offer(new Node(0, 0, 0));

    int[][] cost = new int[501][501];
    for (int i = 0; i < 501; i++) {
      Arrays.fill(cost[i], INF);
    }
    cost[0][0] = 0;

    while (!q.isEmpty()) {
      Node cur = q.poll();
      int r = cur.r;
      int c = cur.c;
      int d = cur.d;

      for (int k = 0; k < 4; k++) {
        int tr = r + dr[k];
        int tc = c + dc[k];
        if (tr < 0 || tr > 500 || tc < 0 || tc > 500 || m[tr][tc] == 2) {
          continue;
        }

        if (m[tr][tc] == 0 && cost[tr][tc] > cost[r][c]) {
          cost[tr][tc] = cost[r][c];
          q.offer(new Node(tr, tc, d));
        } else if (m[tr][tc] == 1 && cost[tr][tc] > cost[r][c] + 1) {
          cost[tr][tc] = cost[r][c] + 1;
          q.offer(new Node(tr, tc, d + 1));
        }
      }
    }

    System.out.println(cost[500][500] == INF ? -1 : cost[500][500]);
  }
}