9328 - 열쇠
본문
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 $h$와 $w$ ($2 \leq h, w \leq 100$)가 주어진다. 다음 $h$개 줄에는 빌딩을 나타내는 $w$개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
- ’.’는 빈 공간을 나타낸다.
- ‘*‘는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
- ’$’는 상근이가 훔쳐야하는 문서이다.
- 알파벳 대문자는 문을 나타낸다.
- 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 “$0$”이 주어진다.
상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.
출력
각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 256MB |
- $1 \leq \text{testcase} \leq 100$
- $1 \leq h, w \leq 100$
풀이
문제는 일반적인 그래프 탐색 문제와 비슷해보인다. 최단경로를 찾는 것도 아니고, 그 때마다 값을 기록해야하는 문제도 아니므로 다익스트라나 dp같은 알고리즘은 필요없고, 일반적인 bfs 탐색으로 문제를 해결할 수 있을 것 같다.
다른 문제와의 차이점이라고 하면, 탐색할 수 있는 공간을 가로막는 문이 있고, 그 문을 열 수 있는 열쇠가 있어야 진행할 수 있다는 점이다. 심지어 그 열쇠도 종류가 여러개라는 점이 문제를 더 어렵게한다.
해결 방법은 일반적인 bfs 탐색를 그대로 사용한다. 서류를 먹었다면 결과값에 $+1$를 한다. 서류를 먹었더라도 그 다음 칸으로 계속 진행할 수 있음을 기억해야한다. 이것은 열쇠를 먹었을 때도 똑같이 적용된다.
분기점은 문이나 열쇠를 맞닥뜨렸을 때이다. 처리 방법은 아래와 같다.
- 문을 만난 경우
- 그 문을 딸 수 있는 열쇠를 이미 가진 경우, 그 문을 빈칸이라고 생각하고 그대로 진행한다
- 그 문을 딸 수 있는 열쇠가 아직 없는 경우, 따로 그 위치를 기록한다
- 열쇠를 만난 경우
- 이미 먹은 열쇠인 경우, 열쇠를 빈칸이라고 생각하고 그대로 진행한다.
- 아직 먹지 않았던 열쇠인 경우, 열쇠를 획득하고 저장했던 문의 위치들 중 열 수 있는 문들을 모두 열었다고 가정하고 탐색을 진행한다.
열쇠를 먹고 그 열쇠에 맞는 문들을 모두 열어 탐색하기 위해, 각 열쇠마다 문의 위치를 저장하는 배열을 따로 생성하여 저장해둔다. 메모리를 많이 쓸 수도 있지만, 열쇠 종류가 최대 26개이고 문의 개수는 많아봤자 1만개이기 때문에 그정도는 사용해도 무방하다.
- 참고 알고리즘 : BFS 탐색
코드
사용 언어 : C
최종 수정일 : 2023 / 1 / 17
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Node {
int x, y;
} ND;
#define MAX_IDX 100
char grid[MAX_IDX][MAX_IDX + 1];
bool visit[MAX_IDX][MAX_IDX];
int h, w;
int document;
#define ALPHABET 26
bool key[ALPHABET];
char keyInput[ALPHABET + 1];
#define DIR 4
ND dir[DIR] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
#define QUEUE_LEN (MAX_IDX * MAX_IDX + 1)
ND queue[QUEUE_LEN];
ND door[ALPHABET][QUEUE_LEN];
int doorLen[ALPHABET];
int front, rear;
#define bigAlphabetIndex(x) ((x) - ('A'))
#define smallAlphabetIndex(x) ((x) - ('a'))
void init() {
front = rear = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
visit[i][j] = false;
}
}
for (int i = 0; i < ALPHABET; ++i) {
key[i] = false;
doorLen[i] = 0;
}
document = 0;
return;
}
bool isValidPosition(ND c) {
return ((0 <= c.x && c.x < h) && (0 <= c.y && c.y < w));
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
init();
scanf("%d %d", &h, &w);
for (int i = 0; i < h; ++i) {
scanf("%s", grid[i]);
}
scanf("%s", keyInput);
for (int i = 0; keyInput[i] > '0'; ++i) {
key[smallAlphabetIndex(keyInput[i])] = true;
}
for (int i = 0; i < w; ++i) {
if (grid[0][i] != '*') {
visit[0][i] = true;
queue[rear++] = (ND){0, i};
}
if (grid[h - 1][i] != '*') {
visit[h - 1][i] = true;
queue[rear++] = (ND){h - 1, i};
}
}
for (int i = 1; i < h - 1; ++i) {
if (grid[i][0] != '*') {
visit[i][0] = true;
queue[rear++] = (ND){i, 0};
}
if (grid[i][w - 1] != '*') {
visit[i][w - 1] = true;
queue[rear++] = (ND){i, w - 1};
}
}
// bfs
while (front < rear) {
ND cur = queue[front++];
char curChar = grid[cur.x][cur.y];
if (curChar == '$') {
++document;
}
if ('a' <= curChar && curChar <= 'z') {
if (key[smallAlphabetIndex(curChar)] == false) {
key[smallAlphabetIndex(curChar)] = true;
for (int i = 0; i < doorLen[smallAlphabetIndex(curChar)]; ++i) {
queue[rear++] = door[smallAlphabetIndex(curChar)][i];
}
}
}
if ('A' <= curChar && curChar <= 'Z') {
if (key[bigAlphabetIndex(curChar)] == false) {
visit[cur.x][cur.y] = true;
door[bigAlphabetIndex(curChar)][doorLen[bigAlphabetIndex(curChar)]++] = cur;
continue;
}
}
for (int i = 0; i < DIR; ++i) {
ND next = (ND){cur.x + dir[i].x, cur.y + dir[i].y};
if (isValidPosition(next) && grid[next.x][next.y] != '*' && visit[next.x][next.y] == false) {
visit[next.x][next.y] = true;
queue[rear++] = next;
}
}
}
printf("%d\n", document);
}
return 0;
}
grid[][]: 입력으로 주어지는 맵의 모습visit[][]: 그 칸을 이미 탐색하였는지 체크하는 용도key[alphabet]: 먹은 열쇠를 기록하는 용도queue[]: 탐색할 수 있는 칸들을 저장하여 bfs를 진행door[alphabet][]: 각 열쇠로 열 수 있는 문들의 위치를 기록