[백준] 17836: 공주님을 구해라! - JAVA

in Algorithm on 그래프 이론

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

풀이

그래프 탐색 문제.

(1, 1)에서 (N, M)까지 최단 시간으로 가야 한다.

T라는 제한 시간이 있고, 벽은 지나갈 수 없으며, 무기를 찾으면 벽도 통과할 수 있다.

즉, 무기가 있고 없고 두 경우를 방문 처리를 따로 해야 하는 문제이다.

class를 만들어 좌표와 시간, 무기가 있는지 정보를 담았다.

bfs 탐색을 통해 (0, 0)부터 진행했다.

시간이 T 초 이상이면 진행을 멈췄고, 그전에 목적지에 도착했으면 출력 후 멈췄다.

사방 탐색 후 다음 칸으로 넘어갈 때 무기가 있는지 없는지에 따라 다르게 처리했다.

메모리: 16148KB

시간: 176ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int r;
        int c;
        int time;
        boolean weapon;

        public Node(int r, int c, int time, boolean weapon) {
            this.r = r;
            this.c = c;
            this.time = time;
            this.weapon = weapon;
        }
    }

    static int[][] vector = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    static int N, M, T;
    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());
        T = Integer.parseInt(st.nextToken());

        board = new int[N][M];
        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());
            }
        }

        System.out.println(bfs());
    }

    private static String bfs() {
        Queue<Node> queue = new LinkedList<>();
        boolean[][][] visit = new boolean[N][M][2];
        queue.add(new Node(0, 0, 0, false));
        visit[0][0][0] = true;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (node.r == N - 1 && node.c == M - 1) {
                return String.valueOf(node.time);
            }

            if (node.time == T) {
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nr = node.r + vector[i][0];
                int nc = node.c + vector[i][1];

                if (nr < 0 || nc < 0 || nr >= N || nc >= M) {
                    continue;
                }

                if (node.weapon) {
                    if (visit[nr][nc][1]) {
                        continue;
                    } else {
                        queue.add(new Node(nr, nc, node.time + 1, true));
                        visit[nr][nc][1] = true;
                    }
                } else {
                    if (visit[nr][nc][0] || board[nr][nc] == 1) {
                        continue;
                    } else if (board[nr][nc] == 2) {
                        queue.add(new Node(nr, nc, node.time + 1, true));
                        visit[nr][nc][0] = true;
                        visit[nr][nc][1] = true;
                    } else {
                        queue.add(new Node(nr, nc, node.time + 1, false));
                        visit[nr][nc][0] = true;
                    }
                }
            }
        }

        return "Fail";
    }

}