알고리즘 문제/[백준]

[백준] 9376 탈옥

latter2005 2021. 1. 12. 05:03

문제 주소 : www.acmicpc.net/problem/9376

 

9376번: 탈옥

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타

www.acmicpc.net

문제 확인

 

그래프 탐색 문제입니다. BFS, 다익스트라 알고리즘으로 해결할 수 있습니다. 맵에서 도달할 수 있는 각 점을 하나의 버텍스로 잡으며 탐색한 후 기록된 값을 이용해 풀 수 있는 문제입니다.

 

풀이

 

죄수 2명과 상근이가 모두 움직이면서 한 점에서 만나는 경우 탈옥을 할 수 있다는 것을 이용합니다. 이 경우 한 점에서 만나는 특성상 정점에서의 각각 문을 연 최솟값이 다른 최솟값에게 영향을 미치지 않습니다. 또한 해당점이 문의 위치인 경우 하나 더 열어야 한다는 점을 주의해야 합니다.

상근이의 경우 태두리의 어느 지점에서라도 감옥으로 진입할 수 있으므로 감옥의 가장자리 부분을 빈 공간으로 만들어 탐색합니다.

따라서 cost[i][j] = 죄수_1[i][j] + 죄수_2[i][j] + 상근[i][j] + (ary[i][j] == '#') 으로 식을 둘 수 있습니다.

cost 배열중 최솟값이 문제의 답이 됩니다.

 

다른 죄수들의 경우에도 탈출을 하더라도 테두리를 계속해서 탐색을 해야 하며 이는 다음과 같은 예외를 처리하기 위함입니다.

*******

#$###$#

*******

위의 경우 가장자리를 탐색하지 않는다면 각자 죄수가 감옥 밖으로 나가 다시 들어오는 경우가 더 적은 비용이 들기 때문에 테두리를 계속해서 탐색해야 합니다.

 

추가로 갈 수 있는 방법이 없는 빈 공간의 경우를 예외처리해 주어야 합니다.

케이스 : www.acmicpc.net/board/view/60596

 

글 읽기 - 데이터를 추가해 주세요

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

이를 위해 cost 값이 초기값인 -1 그대로인 경우를 예외처리 해 주면 됩니다.

 

죄수 2명과 상근이가 모든 맵을 탐색 하면서 각 점에 도달할 때 문을 연 개수의 최솟값을 기록합니다.

다익스트라로 풀 수 있지만 보통 20ms 정도 나오며 이를 단축하기 위해 0-1 BFS 알고리즘을 사용합니다.

0-1 BFS : justicehui.github.io/medium-algorithm/2018/08/30/01BFS/

 

[그래프] 0-1 BFS 알고리즘

어제 알고리즘에 대해 검색을 하다가 코드포스 블로그에서 흥미로운 최단경로 최적화법을 찾아서, 그 방법을 소개하고자 합니다.

justicehui.github.io

간단하게 설명하면 다익스트라에서 사용하는 우선순위 큐에 의해 O(E * logV) 시간이 걸리는 것을 선형 시간 동안 풀 수 있도록 최적화하는 것입니다.

문제에 맞게 알고리즘을 작성해 보면 Depth가 변하는 구간인 벽(#)을 만나는 상황의 우선순위를 낮춰 큐 뒤에 삽입을 하고 depth가 유지되는 빈 공간( . )을 만나는 상황의 우선순위를 높여 큐 앞에 삽입하여 탐색 횟수를 줄입니다.

최종 O(V+E)만큼의 시간이 걸리며 결과 8ms로 단축할 수 있었습니다.

 

0-1 BFS 알고리즘에서 deque 대신 2개의 큐를 이용해 문제를 풀었으며 depth값이 변할 때를 기준으로 큐를 번갈아가며 사용하였습니다. 느린 전역 변수와 포인터 연산을 하지 않도록 함수를 사용하지 않고 main에서 모두 처리하였습니다.

 

코드

 

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
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef struct point {
    int x, y;
    point(int x, int y) :x(x), y(y) {};
}point;
 
int main() {
    short a_cost[102][102], b_cost[102][102], s_cost[102][102];
    char ary[102][102];
    int dx[] = { 001-1 },
        dy[] = { 1-100 };
    queue<point> que[2];
 
    int n, h, w;
    scanf("%d"&n);
    while (n--) {
        scanf("%d%d"&h, &w);
        memset(ary, '.', w + 2);
        int ax = -1, ay, bx, by;
        for (int i = 1; i <= h; i++) {
            ary[i][0= '.';
            scanf("%s", ary[i] + 1);
            for (int j = 1; j <= w; j++) {
                if (ary[i][j] == '$') {
                    if (ax == -1)
                        ax = i, ay = j;
                    else
                        bx = i, by = j;
                }
            }
            ary[i][w + 1= '.';
        }
        memset(ary[h + 1], '.', w + 2);//초기화
 
        bool flag;//배열 뒤집기
        short depth = 0;//문 개수
        memset(a_cost, -1sizeof a_cost);
        a_cost[ax][ay] = 0;//죄수 1
        que[flag = 0].emplace(ax, ay);
        while (!que[0].empty() || !que[1].empty()) {
            if (que[flag].empty())//더이상 문을 열지 않고 탐색할 수 있는 점이 없음
                depth++, flag = !flag;
            int x = que[flag].front().x, y = que[flag].front().y;
            que[flag].pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || h + 1 < nx || ny < 0 || w + 1 < ny || ary[nx][ny] == '*'continue;//벽, 배열 밖
                if (a_cost[nx][ny] == -1) {
                    a_cost[nx][ny] = depth;
                    if (ary[nx][ny] == '#')
                        que[!flag].emplace(nx, ny);//문을 열어야 탐색할 수 있는 위치 => depth ++
                    else
                        que[flag].emplace(nx, ny);//문을 열지 않고 탐색할 수 있는 위치 => depth 같음, 우선 탐색
                }
            }
        }
 
        depth = 0;
        memset(b_cost, -1sizeof b_cost);
        b_cost[bx][by] = 0;//죄수 2
        que[flag = 0].emplace(bx, by);
        while (!que[0].empty() || !que[1].empty()) {
            if (que[flag].empty())
                depth++, flag = !flag;
            int x = que[flag].front().x, y = que[flag].front().y;
            que[flag].pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || h + 1 < nx || ny < 0 || w + 1 < ny || ary[nx][ny] == '*'continue;
                if (b_cost[nx][ny] == -1) {
                    b_cost[nx][ny] = depth;
                    if (ary[nx][ny] == '#')
                        que[!flag].emplace(nx, ny);
                    else
                        que[flag].emplace(nx, ny);
                }
            }
        }
 
        depth = 0;
        memset(s_cost, -1sizeof s_cost);
        s_cost[0][0= 0;//상근
        que[flag = 0].emplace(00);
        while (!que[0].empty() || !que[1].empty()) {
            if (que[flag].empty())
                depth++, flag = !flag;
            int x = que[flag].front().x, y = que[flag].front().y;
            que[flag].pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || h + 1 < nx || ny < 0 || w + 1 < ny || ary[nx][ny] == '*'continue;
                if (s_cost[nx][ny] == -1) {
                    s_cost[nx][ny] = depth;
                    if (ary[nx][ny] == '#')
                        que[!flag].emplace(nx, ny);
                    else
                        que[flag].emplace(nx, ny);
                }
            }
        }
 
        int ans = a_cost[0][0+ b_cost[0][0+ s_cost[0][0];//가장자리 동일한 depth 이므로 한번만 검사
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++) {
                if (s_cost[i][j] != -1) {
                    ans = min(ans, (ary[i][j] == '#'+ s_cost[i][j] + a_cost[i][j] + b_cost[i][j]);
                }
            }
        printf("%d\n", ans);
    }
}
cs
반응형

'알고리즘 문제 > [백준]' 카테고리의 다른 글

[백준] 1086 박성원  (0) 2021.01.15
[백준] 13334 철로  (0) 2021.01.14
[백준] 14891 톱니바퀴  (0) 2021.01.10
[백준] 1444 숌 언어  (0) 2021.01.07
[백준] 15562 네트워크  (0) 2021.01.04