양효원

🏸

문제

  • 아래 조건에 따라 주어지는 지도에서 최단 경로를 구하는 문제이다.
    • 빈 칸, 벽, 문, 열쇠, 출발지, 출구가 주어진다.
    • 문, 열쇠는 각각 A-F, a-f로 주어지고, 대응하는 열쇠가 있어야 문이 있는 위치에 들어갈 수 있다.
    • 문, 열쇠, 출구는 여러 개가 있을 수 있다.
    • 열쇠는 여러 번 사용할 수 있다.
    • 문에 대응하는 열쇠가 없을 수도 있다.
    • 지도의 크기는 최대 50 x 50이다.

풀이

  • DFS로 구현하고, BFS로 구현하면서 시간, 공간 복잡도를 줄였다.
    순서대로 설명하겠다.

BFS 풀이

  • 열쇠가 6개밖에 없기 때문에, 2^6-1의 수로 모든 상태를 표현할 수 있다.
  • 최단 경로 하나만 구하면 되기 때문에, DFS보다 BFS를 사용하여 구현하는 것이 효율적이다.
    • 현재 좌표, 가지고 있는 열쇠 정보에 따라 방문 여부를 저장해야 한다.
  • 처음 출구에 도달하는 것이 최소 경로이기 때문에, 도달하면 탐색을 즉시 종료하면 된다.
BFS 코드 
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

#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define v vector

using namespace std;
using vi = vector<int>;
using ll = long long;
int n, m, di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1}, ans = 70000;
v<string> ar;
v<v<v<bool>>> vis;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int si, sj;
    ar = v<string>(n);
    vis = v<v<v<bool>>>(n, v<v<bool>>(m, v<bool>(63, false)));
    for (int i = 0; i < n; i++) {
        cin >> ar[i];
        for (int j = 0; j < m; j++) {
            if (ar[i][j] == '0')
                si = i, sj = j;
        }
    }
    queue<tuple<int, int, int, char>> q;
    vis[si][sj][0] = true;
    q.push({si, sj, 0, 0});
    while (!q.empty()) {
        auto f = q.front();
        q.pop();
        int ci = get<0>(f), cj = get<1>(f), cd = get<2>(f), ck = get<3>(f);
        if (ar[ci][cj] == '1') {
            ans = cd;
            break;
        }
        for (int i = 0; i < 4; i++) {
            int ni = ci + di[i], nj = cj + dj[i];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m || ar[ni][nj] == '#' || vis[ni][nj][ck]) continue;
            if (ar[ni][nj] >= 'a' && ar[ni][nj] <= 'f') {
                int key = ar[ni][nj] - 'a';
                char tkeys = ck | (0x01 << key);
                vis[ni][nj][tkeys] = true;
                q.push({ni, nj, cd + 1, tkeys});
                continue;
            }
            if (ar[ni][nj] >= 'A' && ar[ni][nj] <= 'F') {
                int key = ar[ni][nj] - 'A';
                if ((ck >> key & 0x01) == 0) continue;
            }
            vis[ni][nj][ck] = true;
            q.push({ni, nj, cd + 1, ck});
        }
    }
    if (ans == 70000)
        cout << -1;
    else
        cout << ans;
    return 0;
}

DFS 풀이

  • 처음에는 열쇠를 주우면 vis 배열의 상태를 초기화한다고 생각했지만, 가진 열쇠 정보에 따라 나눠서 방문 여부를 저장해야 한다.
    • 열쇠를 주울 때마다 vis 배열의 상태를 초기화하면 무한 루프가 발생한다.
      따라서 좌표, 열쇠 정보를 vis 배열에 포함해야 한다.
    • 하나의 변수(si*100000+sj*1000+keys)로 vis 배열에 저장해서, vis 배열의 크기가 굉장히 컸다.
  • 사실 vis 배열의 상태 변수에 열쇠 정보를 추가하면 DFS로 구현할 필요가 없는데, 이전에 떠올린 아이디어(vis 배열 상태 초기화) 때문에 첫 AC는 DFS로 구현한 코드였다.
DFS 코드 
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

#include <iostream>
#include <map>
#include <string>
#include <vector>
#define v vector

using namespace std;
using vi = vector<int>;
using ll = long long;

int n, m, di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1}, ans = 70000;
v<string> ar;
vi vis;

void solve(int si, int sj, char keys) {
    int cidx = si * 100000 + sj * 1000 + keys;
    for (int i = 0; i < 4; i++) {
        int ni = si + di[i], nj = sj + dj[i], nidx;
        nidx = ni * 100000 + nj * 1000 + keys;
        if (ni < 0 || ni >= n || nj < 0 || nj >= m || ar[ni][nj] == '#') continue;
        if (ar[ni][nj] == '1') {
            if (ans > vis[cidx] + 1)
                ans = vis[cidx] + 1;
            continue;
        }
        if (ar[ni][nj] >= 'a' && ar[ni][nj] <= 'f') {
            int key = ar[ni][nj] - 'a', vidx;
            char tkeys = keys | (0x01 << key);
            vidx = ni * 100000 + nj * 1000 + tkeys;
            if (vis[vidx] > vis[cidx] + 1) {
                vis[vidx] = vis[cidx] + 1;
                solve(ni, nj, tkeys);
            }
        } else if (ar[ni][nj] >= 'A' && ar[ni][nj] <= 'F') {
            int key = ar[ni][nj] - 'A';
            if (keys >> key & 0x01 && vis[nidx] > vis[cidx] + 1) {
                vis[nidx] = vis[cidx] + 1;
                solve(ni, nj, keys);
            }
        } else if ((ar[ni][nj] == '.' || ar[ni][nj] == '0') && vis[nidx] > vis[cidx] + 1) {
            vis[nidx] = vis[cidx] + 1;
            solve(ni, nj, keys);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int si, sj;
    ar = v<string>(n);
    vis = vi(10000000, 70000);
    for (int i = 0; i < n; i++) {
        cin >> ar[i];
        for (int j = 0; j < m; j++) {
            if (ar[i][j] == '0')
                si = i, sj = j;
        }
    }
    vis[si * 100000 + sj * 1000] = 0;
    solve(si, sj, 0);
    if (ans == 70000)
        cout << -1;
    else
        cout << ans;
    return 0;
}

풀고나서

  • 큐의 원소로 tuple을 사용하면서 코드의 가독성을 높힐 수 있다는 것을 알게 되었다.
  • bitwise 연산자는 논리 연산자보다 우선순위가 후순위라, 의도에 맞게 쓰려면 순위에 주의해야 한다.

Leave a comment

You may also enjoy

BOJ 1006 - 습격자 초라기

문제 \(2 \times n(1 \le n \le 10000)\)으로 나눠진 구역의 끝부분이 원형으로 연결되어 있다. 한 소대의 인원수 \(W(1 \le W \le 10000)\)와 각 구역 내부 적의 수 \(s_i (1 \le s_i \le W)\)가 주어질 때, 아래...

BOJ 12850 - 본대 산책2

문제 노드가 8개이고 간선의 가중치가 1인 그래프의 그림과 \(D(1 \le D \le 1,000,000,000)\)가 주어질 때, 고정된 0번 노드에서 길이가 D인 closed walk의 개수를 1000000007으로 나눈 나머지를 출력해야 한다. 풀이 그래프의...

BOJ 13460 - 구슬 탈출 2

문제 \(N \times M(3 \le N,\; M \le 10)\)인 보드의 정보가 아래와 같이 주어진다. . : 빈 칸 # : 공이 이동할 수 없는 벽 O : 구멍 R : 빨간 구슬 B : 파란 구슬 ...

BOJ 2252 - 줄 세우기

문제 \(N(1 \le N \le 32000),\; M(1\le M \le 100000)\)이 주어진다. \(N\)개의 정점에 대해 \(M\) 개의 단방향 간선이 주어질 때, 위상 정렬의 경우의 수 중 하나를 출력해야 한다. 풀이 In-degree, DFS를 ...