탈출

📍 문제 설명

 

💡 접근

'고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.' 는 조건만 잘 처리해주고 물이 먼저 이동하도록 하면 풀리는 문제였다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer, cnt, max, min, wall, result = Integer.MAX_VALUE;
    static char[][] board, clone;
    static int[][] dis;
    static boolean[][] visited,successRoute;
    static int[] parent = new int[100001];
    static int[] ch,pm, combi, graph;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Point> list = new ArrayList<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        kb.nextLine();
        board = new char[n][m];
        dis = new int[n][m];
        //빈 곳 - '.' 물 - '*' 돌 - 'X' 비버굴 'D' 고슴도치 'S'
        for(int i = 0; i < n; i++) {
            String s = kb.nextLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = s.charAt(j);
                if(board[i][j] == '*') list.add(new Point(i, j, '*'));
                else if(board[i][j] == 'S') list.add(new Point(i, j, 'S'));
            }
        }
        Collections.sort(list);
        //고슴도치와 물의 위치에서 동시에 퍼진다.
        //물과 고슴도치 따로 위치 저장해놓기
        if(T.solution()) System.out.println(answer);
        else System.out.println("KAKTUS");

    }

    private boolean solution() {
        //큐에 물의 위치 먼저 넣고 고슴도치 위치 넣기
        Queue<Point> q = new LinkedList<>();
        for(Point p : list) q.add(p);
        flag = false;
        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                Point cp = q.poll();
                //일단 물 먼저 퍼지기
                for(int j = 0; j < 4; j++) {
                    int nx = cp.x + dx[j];
                    int ny = cp.y + dy[j];
                    if(nx<0 || ny<0 || nx>=n || ny>=m || board[nx][ny] == 'X' || dis[nx][ny]!=0) continue;
                    //빈칸이면 거리를 기록한다.
                    if(board[nx][ny] == '.') {
                        dis[nx][ny] = dis[cp.x][cp.y] + 1;
                        if(cp.c == 'S') q.offer(new Point(nx, ny, 'S'));
                        else q.offer(new Point(nx,ny, '*'));
                    }
                    //비버의 굴이고 고슴도치가 왔으면 도착!
                    else if(board[nx][ny] == 'D' && cp.c == 'S') {
                        answer = dis[cp.x][cp.y] + 1;
                        flag = true;
                        return;
                    }
                }
            }
        }
        return flag;
    }

    private static class Point implements Comparable<Point> {
        private int x;
        private int y;
        private char c;

        public Point(int x, int y, char c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", c=" + c +
                    '}';
        }

        @Override
        public int compareTo(Point o) {
            return this.c - o.c;
        }
    }
}