[백준 25969] 현대 모비스 자율 주행 시스템 - JAVA

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

 

그리디한 방법은 없으므로 완전 탐색을 한다.

맵이 200 * 200 크기이므로, 재귀를 통한 DFS는 아마 시간초과가 날 것 같다.

대신, BFS를 통해 dis(주행 거리)가 낮은 순으로 탐색하면 처음 도착했을 때 최단 거리임이 보장된다.

 

고려 사항

[중간 지점의 방문 여부 / 패턴 사용횟수 k]에 따라 더 많은 dis를 주행했더라도 최적해일 수 있다.

따라서, vst[N][M][K+1][2] 배열로 기록한다.

 

r, c, k, vstMid가 같은데도 더 많은 dis를 주행했다면 이를 가지치기하며 탐색한다.

 

모호한 조건

한번의 패턴 사용으로 총 n칸을 이동했더라도, dis를 1만 사용한 것으로 가정한다. (문제에 명시x 예제로 유추해야 함)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    int[] dr = {0, 0, -1, 1}, dc = {-1, 1, 0, 0};
    int[][] map = new int[N][M];
    int[][] pattern;

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    List<int[]> patternList = new ArrayList<>();

    for (int i = -2; i <= 2; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = -2; j <= 2; j++) {
        if (st.nextToken().equals("1")) {
          patternList.add(new int[]{i, j});
        }
      }
    }
    int P = patternList.size();
    pattern = new int[P][2];

    for (int i = 0; i < P; i++) {
      pattern[i] = patternList.get(i);
    }

    int[][][][] vst = new int[N][M][K + 1][2];

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        for (int k = 0; k <= K; k++) {
          for (int l = 0; l < 2; l++) {
            vst[i][j][k][l] = 10000000;
          }
        }
      }
    }

    // 구현

    vst[0][0][K][0] = 0;
    Queue<int[]> q = new ArrayDeque<>();

    // 지도의 왼쪽 최상단(시작 지점)은 0임이 보장된다.
    q.offer(new int[]{0, 0, K, 0, 0}); // r, c, k, dis, vstMid;

    while (!q.isEmpty()) {

      int[] info = q.poll();
      int r = info[0];
      int c = info[1];
      int k = info[2];
      int dis = info[3];
      int vstMid = info[4];

      if (r == N - 1 && c == M - 1 && vstMid == 1) {
        System.out.println(dis);
        return;
      }

      // 델타 탐색
      for (int i = 0; i < 4; i++) {
        int tr = r + dr[i];
        int tc = c + dc[i];

        if (tr >= 0 && tr < N && tc >= 0 && tc < M && map[tr][tc] != 1) {

          // 중간 지점을 방문했거나, 다음 지점이 중간 지점인 경우
          int checkMid = vstMid == 1 || map[tr][tc] == 2 ? 1 : 0;

          if (vst[tr][tc][k][checkMid] > dis) {
            vst[tr][tc][k][checkMid] = dis;
            q.offer(new int[]{tr, tc, k, dis + 1, checkMid});
          }
        }
      }

      // 패턴 탐색
      if (k > 0) {
        for (int i = 0; i < P; i++) {
          int tr = r + pattern[i][0];
          int tc = c + pattern[i][1];

          if (tr >= 0 && tr < N && tc >= 0 && tc < M && map[tr][tc] != 1) {

            // 중간 지점을 방문했거나, 다음 지점이 중간 지점인 경우
            int checkMid = vstMid == 1 || map[tr][tc] == 2 ? 1 : 0;

            if (vst[tr][tc][k - 1][checkMid] > dis) {
              vst[tr][tc][k - 1][checkMid] = dis;
              q.offer(new int[]{tr, tc, k - 1, dis + 1, checkMid});
            }
          }
        }
      }
    }
    System.out.println(-1);
  }
}