(백준) 호석사우루스 - 22255 [JAVA]

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

22255번: 호석사우루스

 

🐢 해설

방문처리가 복잡했던 문제였다. 

 

무엇보다 첫번째 시작이 1번이고 이동하는 횟수 N번이 3N, 3N + 1, 3N + 2에 따라서 이동할 수 있는 방향이 달라지는 것이 중요했다.

-> 이동횟수 별 탐색 방향 : (N % 3 == 1 : 상하, N % 3 == 2 : 좌우, N % 3 == 0 : 상하좌우)

 

한번 방문 했다고 바로 방문 처리를 하면 안될 뿐더러 특정 방향을 가질때 어디로 이동했냐에 따라 다른 결과를 낳으므로 이동방향까지도 확인을 해줘야한다.

 

따라서 움직이는 호석 객체에 탐색방향을 위한 현재 탐색 번호 (0, 1, 2), 호석이의 좌표, 해당 호석이가 움직이면서 받은 데미지를 갖게 했으며, 방문 체크는 현재 호석이가 움직이는 방향, 탐색 번호 (0, 1, 2), 좌표 값을 이용해서 했다.

 

이때 호석이는 데미지가 적게 받은 것부터 우선탐색하기 위해 우선순위 큐를 사용했다.

 

🐢 코드

import java.io.*;
import java.util.*;

public class 호석사우루스_22255 {
    static int N, M, ans = 0;
    static boolean[][][][] visited;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];
        visited = new boolean[4][3][N][M]; // 이동방향, 탐색 경우 , y, x

        String[] input = br.readLine().split(" ");
        int sy = Integer.parseInt(input[0])-1;
        int sx = Integer.parseInt(input[1])-1;
        int ey = Integer.parseInt(input[2])-1;
        int ex = Integer.parseInt(input[3])-1;
        Dot start = new Dot(1, sy, sx, 0);

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        board[ey][ex] = 400;
        BFS(start);
        if (ans == 0) System.out.println(-1);
        else System.out.println(ans);
    }

    private static void BFS(Dot start) {
        PriorityQueue<Dot> pq = new PriorityQueue<>(Comparator.comparingInt(d -> d.d));
        pq.add(start);

        while (!pq.isEmpty())
        {
            Dot now = pq.poll();
            int move = now.m;

            int d = 0, ed = 4;
            if (move % 3 == 1) ed = 2;
            else if (move % 3 == 2) d = 2;

            for (; d < ed; d++) {
                int ny = now.y + dy[d];
                int nx = now.x + dx[d];

                if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
                if (board[ny][nx] == -1) continue;
                if (visited[d][move][ny][nx]) continue;
                if (board[ny][nx] == 400) {
                    ans = now.d;
                    return;
                }

                visited[d][move][ny][nx] = true; // 이동방향, 탐색 경우 , y, x
                pq.add(new Dot((move+1) % 3, ny, nx, now.d + board[ny][nx]));
            }
        }
    }

    private static class Dot
    {
        int m, y, x, d;

        public Dot(int m, int y, int x, int d) {
            this.m = m;
            this.y = y;
            this.x = x;
            this.d = d;
        }
    }
}