본문 바로가기

ProgramSoliving

백준 : 9376

반응형

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

 

9376번: 탈옥

문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어

www.acmicpc.net

처음 접근햇던 방식은 죄수 두명을 각각 큐에 넣어서 탈출할수 있는 경로를 구하고 그경로를 가지고 각각 대조햇을때 겹치는 부분을 제거하는식으로 구할려고 하였다. 하지만 이러한경우 너무많은 case로 인해서 시간초과가 난다.

문제를 풀기위해서는 아이디어가 필요하다. map을 N+2 M+2 크기로 잡아서 외벽에도 공간이 있다고 한다면

바깥족에서 접근하는 사람 1, 죄수 2명 총 3사람을 가지고 BFS를 이용해서 map에 최단경로를 만들수가있다.

이렇게 3명에대한 최단경로를 가지고 전부다를 sum 햇을때를 생각해보자. 죄수 세명이 문을 열어 탈출할수 있는 최단경로는 세며의 사람이 각각 문을 열면서 갈때 어느 하나의 문에서 만날때가  최단으로 문을여고 탈출하는 경우다. 

따라서 각각의 sum을 구하고 $ 지점에서 최단값을 찾으면된다. 이때 답은 -2를 해주면된다 세명이 마지막 겹치는 점에서 문을 열기때문이다.

그러면 문을 안열고 나갈수도 있지않은가?? 이러한경우는 0,0 지점에 값을 비교해주면된다. 죄수세명이 #을 하나도 거치지않고 나갓다면 0,0 인지점에서 값을 비교하면 되기때문이다
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
package day0304;
 
 
 
public class B9376 {
    static int T;
    static int N, M;
    static char[][] map;
    static int[][] digit;
    static int[][] sumDigit;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
 
            map = new char[N + 2][M + 2];
            sumDigit = new int[N + 2][M + 2];
 
            for (int i = 0; i < N + 2; i++) {
                Arrays.fill(map[i], '.');
            }
 
            for (int i = 1; i <= N; i++) {
                char c[] = br.readLine().toCharArray();
                for (int j = 1; j <= M; j++) {
                    map[i][j] = c[j - 1];
                }
            }
 
            BFS(00);
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j < M; j++) {
                    if (map[i][j] == '$')
                        BFS(i, j);
                }
            }
 
            int Answer = sumDigit[0][0];
 
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if(map[i][j]=='#') {
                        Answer = Math.min(Answer, sumDigit[i][j]-2);
                    }
                        
                    
                }
            }
            System.out.println(Answer);
 
        }
    }
 
    static class Pair {
        int y;
        int x;
        int w;
 
        public Pair(int y, int x, int w) {
            super();
            this.y = y;
            this.x = x;
            this.w = w;
        }
    }
 
    static int dy[] = { 1-100 };
    static int dx[] = { 001-1 };
 
    static void BFS(int y, int x) {
        digit = new int[N + 2][M + 2];
        for (int i = 0; i < N + 2; i++) {
        }
 
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(y, x, 0));
        digit[y][x] = 0;
 
        while (!q.isEmpty()) {
 
            Pair tmp = q.poll();
 
            for (int d = 0; d < 4; d++) {
                int ny = tmp.y + dy[d];
                int nx = tmp.x + dx[d];
 
                if (ny < 0 || nx < 0 || ny >= N + 2 || nx >= M + 2)
                    continue;
                if (map[ny][nx] == '*')
                    continue;
                int next = (map[ny][nx] == '#') ? 1 : 0;
                next += tmp.w;
 
                if (digit[ny][nx] > next) {
                    digit[ny][nx] = next;
                    q.add(new Pair(ny, nx, next));
                }
            }
        }
 
        for (int i = 0; i < N + 2; i++) {
            for (int j = 0; j < M + 2; j++) {
                if(map[i][j]=='*')continue;
                sumDigit[i][j] += digit[i][j];
            }
        }
 
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
반응형

'ProgramSoliving' 카테고리의 다른 글

벨만포드 알고리즘 : 백준 11657 ( 타임머신)  (0) 2020.03.08
백준 : 1039 JAVA  (0) 2020.03.07
백준 : 2933 JAVA  (0) 2020.03.03
백준 : 10830  (0) 2020.03.02
백준 : 11401  (0) 2020.03.02