[백준/자바] #17836

이전의 파이썬 풀이의 로직을 그대로 적용해봤는데, 중간에 자꾸 Fail이 났다. 결국 다른 풀이를 참고해서 풀었다. 아쉬운 마음에 풀었던 기록이라도 남겨본다. 

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


class Main {

    static class Item implements Comparable<Item> {
        int x;
        int y;
        int time;
        public Item(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }

        @Override
        public int compareTo(Main.Item o) {
            if (this.time > o.time) {
                return 1;
            } else if (this.time < o.time) {
                return -1;
            }
            if (this.x > o.x) {
                return 1;
            } else if (this.x < o.x) {
                return -1;
            }
            if (this.y > o.y) {
                return 1;
            } else if (this.y < o.y) {
                return -1;
            }
            return 0;
        }
    }

    static int N, M, T;
    static int[][] graph;
    static boolean[][] visited;
    static int gramX, gramY;
    static PriorityQueue<Item> priorityQueue;
    static final int[] dx = {0, 0, 1, -1};
    static final int[] dy = {1, -1, 0, 0};
    static final int EMPTY = 0;
    static final int WALL = 1;
    static final int GRAM = 2;
    static final int INF = 100000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input1 = br.readLine().split(" ");
        N = Integer.parseInt(input1[0]);
        M = Integer.parseInt(input1[1]);
        T = Integer.parseInt(input1[2]);
        graph = new int[N][M];
        visited = new boolean[N][M];
        priorityQueue = new PriorityQueue<>();
        
        for(int i=0; i<N; i++) {
            String[] input2 = br.readLine().split(" ");
            for(int j=0; j<M; j++) {
                graph[i][j] = Integer.parseInt(input2[j]);
                if (graph[i][j] == GRAM) {
                    gramX = i;
                    gramY = j;
                }
            }
        }
        br.close();

        int startToGram = find(gramX, gramY);
        int startToPrincess = find(N-1, M-1);
        int gramToPrincess = (N-1-gramX) + (M-1-gramY);

        if (startToGram == INF && startToPrincess == INF) {
            System.out.println("Fail");
        } else {
            int minDistance = Math.min(startToPrincess, startToGram + gramToPrincess);
            if (minDistance <= T) {
                System.out.println(minDistance);
            } else {
                System.out.println("Fail");
            }
        }
    }

    private static int find(int endX, int endY) {
        priorityQueue.add(new Item(0, 0, 0));
        visited[0][0] = true;
        while(!priorityQueue.isEmpty()) {
            Item item = priorityQueue.poll();
            if (item.x == endX && item.y == endY) {
                return item.time;
            }
            for(int k=0; k<4; k++) {
                int nx = item.x + dx[k];
                int ny = item.y + dy[k];
                if (0 <= nx && nx < N && 0 <= ny && ny < M && graph[nx][ny] != WALL && !visited[nx][ny]) {
                    priorityQueue.add(new Item(nx, ny, item.time + 1));
                    visited[nx][ny] = true;
                }
            }
        }
        return INF;
    }
}

 

참고한 풀이는 다음과 같다. 

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 int N, M, T;
    static int answer = 10001;
    static int[][] map;
    static boolean[][] visited;
    static int[][] deltas = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static Position sword;

    static class Position {
        int r, c;

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

    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[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());
                if (map[i][j] == 2) sword = new Position(i, j);
            }
        }

        bfs();

        System.out.println(answer > T ? "Fail" : answer);
    }

    static void bfs() {
        Queue<Position> queue = new LinkedList<>();
        queue.offer(new Position(0, 0));
        visited[0][0] = true;
        int count = -1;
        int size = 0;
        while (!queue.isEmpty()) {
            count++;
            size = queue.size();
            for (int step = 0; step < size; step++) {
                Position temp = queue.poll();

                if (temp.r == sword.r && temp.c == sword.c) {
                    answer = count + N - 1 - sword.r + M - 1 - sword.c;
                    continue;
                } else if (temp.r == N - 1 && temp.c == M - 1) {
                    answer = Math.min(answer, count);
                    return;
                }

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

                    if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] != 1) {
                        queue.offer(new Position(nr, nc));
                        visited[nr][nc] = true;

                    }
                }
            }
        }
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }
}