[백준] 1261번 탈출

1) 생각

우선 이동해야하는것이 2가지이다. 하나는 고슴도치(S)이고 다른 하나는 물(*)이다. 비버(D)와 돌(X)은 움직이지 않으므로 if 문 처리만 잘 해주고 신경쓰지 않는다.

침수 예정 지역으로 고슴도치가 이동해서는 안되므로 맨 처음에 물을 먼저 퍼트리는것이 편하다 생각하였다.

2) 방안

물을 맨 처음 퍼트리면 이것은 예상 경로를 미리 놓은 것이기 때문에 물이 한 턴 앞서나가게된다. 따라서 반복문에 들어가기전 한 번 수행후 물의 퍼트림을 1번 쉬어줌으로서 맨 처음 예상 침수 경로만 만들어 놓고 진행하였다. 

물의 경우 마지막 퍼트린 지점만 알고있으면 되고, 또 물이 처음에 여러개 등장할 수 있으므로 list로 만들어준후 이전 좌표를 List에서 제거하면서 생성하였다.

고슴도치와 물의 이동경로 좌표를 위해서 class를 따로 만들어주었는데 하나로 통합하고 물은 카운트 값이 cnt를 0으로 넣어도 상관 없을것같다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
 
public class Main{
    static int r,c;
    static int dx,dy,sx,sy;
    static List<Water> wList;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
        int[][] arr = new int[r][c];
        wList = new ArrayList<>();        
        for(int i=0;i<r;i++) {
            String t = sc.next();
            for(int j=0;j<c;j++) {
                arr[i][j] = t.charAt(j);
                if(arr[i][j]=='D') {
                    dx = i;
                    dy = j;
                }else if(arr[i][j]=='S') {
                    sx = i;
                    sy = j;
                }else if(arr[i][j]=='*')
                    wList.add(new Water(i,j));
            }
        }        
        visited = new boolean[r][c];
        System.out.println(solve(arr));
    }
    
    static boolean[][] visited;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static String solve(int[][] arr) {
        Queue<Move> queue = new LinkedList<>();
        queue.add(new Move(sx,sy,0));
        visited[sx][sy] = true;
        int min = Integer.MAX_VALUE;
        boolean flag = false;
        boolean con = false;
        // 침수 예정 지역을 갈 수 없으므로 물을 먼저 늘려준다.
        moveWater(arr);
 
        while(!queue.isEmpty()) {
            int size = queue.size();
            // 먼저 늘렸으므로 한 번 쉬기
            if(con) moveWater(arr);
            for(int i=0;i<size;i++) {
                Move t = queue.poll();
                if(t.x==dx&&t.y==dy) {
                    min = Math.min(min, t.cnt);
                    flag = true;
                    break;
                }
                visited[t.x][t.y] = true;
                for(int j=0;j<4;j++) {
                    int tx = t.x+dir[j][0];
                    int ty = t.y+dir[j][1];
                    if(tx<0 || ty<0 || tx>=r || ty>=c) continue;
                    if(arr[tx][ty]=='X' || arr[tx][ty]=='*' || arr[tx][ty]=='S') continue;
                    if(!visited[tx][ty]) {
                        queue.add(new Move(tx,ty,t.cnt+1));
                        arr[tx][ty] = 'S';
                    }
                }
            }
            con = true;
            if(flag) break;
        }
        if(min==Integer.MAX_VALUE) return "KAKTUS";
        return min+"";
    }
    
    private static void moveWater(int[][] arr) {
        int size = wList.size();
        for(int i=0;i<size;i++) {
            Water t = wList.get(0);
            wList.remove(0);
            for(int j=0;j<4;j++) {
                int tx = t.x + dir[j][0];
                int ty = t.y + dir[j][1];
                if(tx<0 || ty<0 || tx>=r || ty>=c) continue;
                if(arr[tx][ty]=='X' || arr[tx][ty]=='*' || arr[tx][ty]=='D') continue;
                arr[tx][ty] = '*';
                wList.add(new Water(tx,ty));
            }
        }
    }
    
    static class Move{
        private int x;
        private int y;
        private int cnt;
        public Move(int x,int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    static class Water{
        private int x;
        private int y;
        public Water(int x,int y) {
            this.x = x;
            this.y = y;
        }
    }
}