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

문제 바로가기 : https://www.acmicpc.net/problem/17836

메모리 : 16472KB

시간 : 188ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Node {
        int r, c, d;
        boolean gram;

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

    public static <T> 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 T = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M];
        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());
            }
        }
        int[][] vector = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        Queue<Node> q = new LinkedList<>();
        int ans = Integer.MAX_VALUE;
        boolean[][][] check = new boolean[N][M][2];
        q.add(new Node(0, 0, 0, false));
        check[0][0][0] = true;

        while (!q.isEmpty()) {
            Node n = q.poll();
            if (n.d > T || n.d > ans) {
                continue;
            }
            for (int k = 0; k < 4; k++) {
                int x = n.r + vector[k][0];
                int y = n.c + vector[k][1];
                if (x >= 0 && y >= 0 && x < N && y < M) {
                    // 공주 줍기 가장빠른시간
                    if (x == N - 1 && y == M - 1) {
                        ans = Math.min(ans, n.d + 1);
                    }
                    // 검이 있으면 벽뚫기
                    if (n.gram && !check[x][y][1]) {
                        check[x][y][1] = true;
                        q.add(new Node(x, y, n.d + 1, n.gram));
                    } else {
                        if (map[x][y] == 2 && !check[x][y][0]) {
                            // 그램 줍기
                            check[x][y][0] = check[x][y][1] = true;
                            q.add(new Node(x, y, n.d + 1, true));
                        } else if (map[x][y] == 0 && !check[x][y][0]) {
                            // 벽없는곳으로 이동
                            check[x][y][0] = true;
                            q.add(new Node(x, y, n.d + 1, n.gram));
                        }
                    }
                }
            }
        }
        if (ans == Integer.MAX_VALUE) {
            System.out.println("Fail");
        } else {
            System.out.println(ans);
        }
    }
}

풀이

너비우선탐색으로 간 거리를 체크하며 공주에게 닿았을 때 가장 짧은 시간을 찾으면 된다. 주의해야할 점은 방문체크인데, 처음에 이차원 배열로 처리했을떄는 메모리초과가 발생했다..! 어떤 칸을 갈 수 있는 모든 노드에서 칸을 방문한 후 true처리가 되기 때문에 아무래도 큐에 들어가는 수가 많아지는 것 같았다. 그래서 3차원배열을 이용해 좌표와 "그램"을 가지고 방문한 칸=벽을 뚫을 수 있다. 그램없이 방문한 칸을 나누어 체크해주었다.

추가적으로 문제에 그램에 대한 정보가 맵에서 딱 한 번 반드시 등장한다는 것이었는데, 이는 (1.1) 칸에도 등장할 수 있음을 의미하는 것이 아닐까???? 그래서 이에 대한 처리를 해줬었는데 문제에 해당 테스트케이스는 없는 것으로 보인다.ㅋ