백준 5827번: What's Up With Gravity (Java)

접근

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

5827번: What's Up With Gravity

문제 해석 : Captain Bovidian 이 Doctor Beefalo 를 찾아 떠납니다. 맵 전체에는 아래 방향으로 중력이 작용하고 있어 Bovidian 은 좌, 우 방향으로만 움직일 수 있고, 움직이는 중간에 공중으로 이동한다면 공중에 떠있지 못하고 중력 방향으로 바로 떨어지게 됩니다. 그대신 Bovidian 은 중력의 방향을 바꿀 수 있는 능력을 가지고 있고, 중력의 방향을 바꾸게 되면 기존에 천장이었던 곳으로 떨어지게 됩니다. Bovidian 이 Beefalo 에 도달할 수 있는 최소의 중력 전환의 수를 구하면 되는 문제이고, 중력을 아무리 전환해도 목적지에 도달할 수 없다면 -1을 출력하도록 합니다.

BFS를 할 때, 일반 LinkedList 가 아닌 PriorityQueue 를 이용하여 flip(중력 전환 수)를 기준으로 정렬하여 BFS를 진행하여 문제를 해결할 수 있습니다. 그렇게 진행함으로써 목적지에 도달할 수 있는 가장 작은 flip의 수를 구할 수 있습니다.

visited 배열은 visited[N][M][2] 로 초기화합니다. 첫번째 N * M 배열에는 중력이 정방향일 때(flip % 2 == 0), 두번째 배열에는 중력이 역방향일 때(flip % 2 == 1) 의 방문 정보를 저장해주었습니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static int R, C;
  static char[][] map;
  static boolean gravity_flipped = false;
  static int sr, sc, er, ec;
  static int dc[] = { 1, -1 };

  static class Node implements Comparable<Node> {

    private int r, c, flipped;

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

    @Override
    public int compareTo(Node o) {
      return this.flipped - o.flipped;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] rc = br.readLine().split(" ");
    R = Integer.parseInt(rc[0]);
    C = Integer.parseInt(rc[1]);
    map = new char[R][C];
    for (int i = 0; i < R; i++) {
      String input = br.readLine();
      for (int j = 0; j < C; j++) {
        map[i][j] = input.charAt(j);
        if (map[i][j] == 'C') {
          map[i][j] = '.';
          sr = i;
          sc = j;
        } else if (map[i][j] == 'D') {
          map[i][j] = '.';
          er = i;
          ec = j;
        }
      }
    }
    br.close();
    int res = startAdventure();
    System.out.println(res);
  }

  static boolean outMap(int r, int c) {
    return (r < 0 || R <= r || c < 0 || C <= c);
  }

  static int startAdventure() {
    boolean[][][] visited = new boolean[R][C][2];
    PriorityQueue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(sr, sc, 0));
    visited[sr][sc][0] = true;
    while (!queue.isEmpty()) {
      Node now = queue.poll();
      boolean out = false;
      if (now.r == er && now.c == ec) return now.flipped;
      int nowr = now.r;
      if (now.flipped % 2 == 1) {
        while (true) {
          if (nowr <= 0) {
            out = true;
            break;
          }
          if (map[nowr - 1][now.c] == '#') {
            break;
          }
          if (nowr - 1 == er && now.c == ec) {
            return now.flipped;
          }
          nowr--;
        }
      } else {
        while (true) {
          if (R - 1 <= nowr) {
            out = true;
            break;
          }
          if (map[nowr + 1][now.c] == '#') {
            break;
          }
          if (nowr + 1 == er && now.c == ec) {
            return now.flipped;
          }
          nowr++;
        }
      }
      if (out) continue;
      if (visited[nowr][now.c][(now.flipped + 1) % 2] == false) {
        queue.add(new Node(nowr, now.c, now.flipped + 1));
        visited[nowr][now.c][(now.flipped + 1) % 2] = true;
      }
      int nc = now.c + 1;
      if (nc < C && (map[nowr][nc] != '#') && visited[nowr][nc][now.flipped % 2] == false) {
        queue.add(new Node(nowr, nc, now.flipped));
        visited[nowr][nc][now.flipped % 2] = true;
      }
      nc = now.c - 1;
      if (0 <= nc && (map[nowr][nc] != '#') && visited[nowr][nc][now.flipped % 2] == false) {
        queue.add(new Node(nowr, nc, now.flipped));
        visited[nowr][nc][now.flipped % 2] = true;
      }
    }
    return -1;
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!