[JAVA] 백준 1445 - 일요일 아침의 데이트

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

N X M 크기의 map에서 S 부터 F까지 갈 때, 최대한 쓰래기를 적게, 그리고 쓰래기 주변을 최대한 적게 밟고 F까지 도달할 때 밟는 쓰래기의 수와 쓰래기 주변을 지나가는 수를 출력하는 문제이다.

 

처음에는 우선순위 큐 정렬 기준을 최대한 쓰래기를 피하도록 짰다가 한 번 틀리고, 쓰래기가 주변에 있는 쓰래기 칸의 경우 쓰래기 주변을 밟는 카운트를 올리면 안된다는 것을 적용해서 성공했다.

 

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

public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        char[][] map = new char[info[0]][info[1]];
        int starti = 0;
        int startj = 0;
        for (int i = 0; i < map.length; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 'S') {
                    starti = i;
                    startj = j;
                }
            }
        }
        Forest start = new Forest(starti, startj);
        start.t = 0;
        start.nt = 0;
        boolean[][] visited = new boolean[info[0]][info[1]];
        PriorityQueue<Forest> pq = new PriorityQueue<>();
        pq.offer(start);
        while (!pq.isEmpty()) {
            Forest target = pq.poll();
            int i = target.i;
            int j = target.j;
            if (visited[i][j]) continue;
            visited[i][j] = true;
            if (map[i][j] == 'F') {
                System.out.println(target.t + " " + target.nt);
                return;
            }
            for (int k = 0; k < 4; k++) {
                if (check(i + dx[k], j + dy[k], map, visited)) {
                    Forest route = new Forest(i + dx[k], j + dy[k]);
                    route.calc(map);
                    route.nt = route.nearTrash ? target.nt + 1 : target.nt;
                    route.t = route.trash ? target.t + 1 : target.t;
                    pq.offer(route);
                }
            }
        }

    }

    static boolean check(int i, int j, char[][] map, boolean[][] visited) {
        if (i < 0 || i >= map.length) return false;
        if (j < 0 || j >= map[0].length) return false;
        return !visited[i][j];
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Forest implements Comparable<Forest> {
    int i;
    int j;
    boolean trash = false;
    boolean nearTrash = false;
    int t = Integer.MAX_VALUE;
    int nt = Integer.MAX_VALUE;

    Forest(int i, int j) {
        this.i = i;
        this.j = j;
    }

    void calc(char[][] map) {
        if (map[this.i][this.j] == 'F') {
            this.trash = false;
            this.nearTrash = false;
            return;
        }
        if (map[this.i][this.j] == 'g') {
            this.trash = true;
            return;
        }
        boolean flag = false;
        if (i < map.length - 1) {
            if (map[i + 1][j] == 'g') flag = true;
        }
        if (i > 0) {
            if (map[i - 1][j] == 'g') flag = true;
        }
        if (j < map[0].length - 1) {
            if (map[i][j + 1] == 'g') flag = true;
        }
        if (j > 0) {
            if (map[i][j - 1] == 'g') flag = true;
        }
        this.nearTrash = flag;
    }

    @Override
    public int compareTo(Forest o) {
        int c = this.t - o.t;
        if (c == 0) return this.nt - o.nt;
        else return c;
    }
}