알고리즘31 :: BOJ_3055_탈출

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    private static int n,m;
    private static String[][] map;
    private static int[][] waterTime;
    private static int[][] hedgehogTime;
    private static int x,y,x2,y2,x3,y3;
    private static int ans = Integer.MAX_VALUE;
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,-1,1};
    private static Queue<int[]> wq = new LinkedList<>();
    private static void BFS() { //물 
        
        while(!wq.isEmpty()) {
            int[] pos = wq.remove();
            int gox = pos[0];
            int goy = pos[1];
            
            for(int i=0; i<4; i++) {
                int ddx = gox + dx[i];
                int ddy = goy + dy[i];
                
                if(ddx<0 || ddx>=n || ddy<0 || ddy>=m) continue;
                
                if(waterTime[ddx][ddy] == 0 && !map[ddx][ddy].equals("X") && !map[ddx][ddy].equals("D")) {
                    waterTime[ddx][ddy] = waterTime[gox][goy] + 1;
                    wq.add(new int[] {ddx,ddy});
                }
            }
            
        }
    }
    private static void BFS2(int xt, int yt) { // 고슴도치 
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {xt,yt});
        hedgehogTime[xt][yt] =1;
        while(!q.isEmpty()) {
            int[] pos = q.remove();
            int x = pos[0];
            int y = pos[1];
            
            for(int i=0; i<4; i++) {
                int ddx = x + dx[i];
                int ddy = y + dy[i];
                
                if(ddx<0 || ddx>=n || ddy<0 || ddy>=m) continue;
                
                if(hedgehogTime[ddx][ddy] == 0 && 
                        !map[ddx][ddy].equals("X") && (hedgehogTime[x][y]+1 < waterTime[ddx][ddy] || waterTime[ddx][ddy] == 0)) {
                    
                    hedgehogTime[ddx][ddy] = hedgehogTime[x][y]+1;
                    q.add(new int[] {ddx,ddy});
                }
                if(map[ddx][ddy].equals("D")) {
                    
                    if(ans>hedgehogTime[x][y]+1)
                        ans = hedgehogTime[x][y]+1;
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new String[n][m];
        
        /**
         * 고슴도치 위치  = S
         */
        
        x=0;
        y=0;
        
        /**
         * 
         * 물의 위 = * 
         */
        x2 = 0;
        y2 = 0;
        
        /** 비버의 집 위치
         * 
         * 
         * 
         * 
         */
        x3 = 0;
        y3 = 0;
 
        waterTime = new int[n][m];
        for(int i=0; i<n; i++) {
            String str = br.readLine();
            for(int j=0; j<m; j++) {
                map[i][j] = str.substring(j, j+1);
                //System.out.print(map[i][j]+" ");
                if(map[i][j].equals("S")) {
                    x = i;
                    y = j;
                }
                if(map[i][j].equals("*")) {
                    
                    x2=i;
                    y2=j;
 
                    waterTime[x2][y2] = 1;
                    wq.add(new int[] {x2,y2});
                    
                }
                if(map[i][j].equals("D")) {
                    x3 = i;
                    y3 = j;
                }
            }
            //System.out.println();
        }//end of for loop
        
        
        BFS();
        
        hedgehogTime = new int[n][m];
        BFS2(x,y);
        
        if(ans == Integer.MAX_VALUE)
            System.out.println("KAKTUS");
        else
            System.out.println(ans-1);
        
    }
 
}

이 문제 접근은 다음과 같습니다.

1. visit 대신에 물의 시간을 waterTime에 저장 합니다. 물론 시작 지점은 0 으로 해도 좋으나, 나중에 map[ddx][ddy] == 0 이런 조건 땜에 0 이 업데이트 되는 경우가 발생합니다. 그래서 1부터 시작했습니다.

2. 물을 이동시켰으면 고슴도치를 이동시킵니다. 단 고슴도치가 이동할때도 시작지점의 시간은 1로 잡아줬으며 물의 시간보다 작은 경우만 탐색했습니다. 

이게 포인트 인데 ...

틀렸습니다가 뜬 이유를 잡고보니 다음과 같았습니다.

 

1. 물의 개수가 여러개 인경우

2. 모두 벽으로 막혀있는 공간안에 물이 있어서, 고슴도치가 이동할때 물의 시간으로 조건을 준 경우 탈출 하지 못하는 경우가 발생했습니다. 

 

이 두개만 잘 처리해서 ac 받았습니다.