1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class 탈출 {
 
    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(int x2, int y2) { //물 
        
        waterTime[x2][y2] = 1;
        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;
 
        
        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;
 
                    
                    wq.add(new int[] {x2,y2});
                    
                }
                if(map[i][j].equals("D")) {
                    x3 = i;
                    y3 = j;
                }
            }
            //System.out.println();
        }//end of for loop
        waterTime = new int[n][m];
        BFS(x2,y2);
        
        hedgehogTime = new int[n][m];
        BFS2(x,y);
        
        if(ans == Integer.MAX_VALUE)
            System.out.println("KAKTUS");
        else
            System.out.println(ans-1);
        
    }
 
}
 
 cs

탈출 문제는 시간 이 핵심이다.

 

물을 먼저 BFS로 이동시킨다. 한칸 이동할 때마다 +1 씩 증가한다. 

 

이후 고슴도치를 이동시킨다. 한칸 이동할 때마다 마찬가지로 +1 씩 증가한다. 하지만, 고슴도치가 다음에 이동할 시간이 해당 칸에서 물이 지나간 시간보다 크다면 !

 

물이 먼저 도착하고 고슴도치가 이동하는 위치이기 때문에 도달 불가능하다.

 

이러한 점에서 탐색을 진행하고 고슴도치를 D 위치까지 도달하면 문제를 해결 할 수 있다. 

'알고리즘' 카테고리의 다른 글

알고리즘76 :: BOJ_7576_토마토  (0) 2020.03.11
알고리즘75 :: BOJ_6603_로또  (0) 2020.03.11
알고리즘73 : : BOJ_1316_그룹단어체커  (0) 2020.02.28
알고리즘72 :: BOJ_17143_낚시왕  (0) 2020.02.28
알고리즘71 :: BOJ_1541_잃어버린 괄호  (1) 2020.02.28

다른 글

  • 알고리즘76 :: BOJ_7576_토마토
  • 알고리즘75 :: BOJ_6603_로또
  • 알고리즘73 : : BOJ_1316_그룹단어체커
  • 알고리즘72 :: BOJ_17143_낚시왕
다른 글 더 둘러보기

티스토리툴바