백준
백준 9328 열쇠
콩순이냉장고
2022. 3. 29. 00:23
문제 URL : https://www.acmicpc.net/problem/9328
9328번: 열쇠
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가
www.acmicpc.net
문제접근법 : $를 얼마나 획득할수 있는지 물어보는 문제입니다.
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include<bits/stdc++.h>
using namespace std;
#define v vector
#define vc v<char>
#define vvc v<vc>
int n, m;
vvc board;
string s;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
board = vvc(n + 2, vc(m + 2, '.'));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
}
}
cin >> s;
}
bool isrange(int y, int x) {
return 0 <= y && y < n + 2 && 0 <= x && x < m + 2;
}
void solve() {
int key = 0;
for (char c : s)
if (c != '0')key |= 1 << (c - 'a');
vvc check(n + 2, vc(m + 2));
queue<pair<int, int>> q;
q.push({ 0,0 });
check[0][0] = 1;
int res = 0;
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && check[ny][nx]==0) {
if (board[ny][nx] == '.'||board[ny][nx]=='$') {
q.push({ ny,nx });
if (board[ny][nx] == '$') {
res++;
board[ny][nx] = '.';
check = vvc(n + 2, vc(m + 2));
}
check[ny][nx] = 1;
}
else if ('a' <= board[ny][nx] && board[ny][nx] <= 'z') {
q.push({ ny,nx });
if (!(1 << (board[ny][nx] - 'A') & key)) {
key |= 1 << (board[ny][nx] - 'a');
check = vvc(n + 2, vc(m + 2));
}
check[ny][nx]=1;
}
else if ('A' <= board[ny][nx] && board[ny][nx] <= 'Z') {
if (1 << (board[ny][nx] - 'A') & key) {
q.push({ ny,nx });
check[ny][nx] = 1;
}
}
}
}
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
int test;
cin >> test;
while (test--) {
input();
solve();
}
}
|
cs |
답은 맞고 간단하지만 시간이 그렇게 빠르지 않다라는걸 직관적으로 알수있습니다.
더 빠르게 할수 있는 방법을 생각해 보죠
bfs든 dfs든 이전에 왔던곳을 재방문 하지 않도록 하는것이 원칙인데 계속해서 check를 초기화하는것은
느리다는것을 분명합니다. 그렇지만 키는 26개이니 bit마스크로 어떻게 방문했는지 check를 더 주게된다면
최대 100*100*2^26 이 되버려 메모리 상으로 매우 안좋게 됩니다.
그렇다면 어떻게 해결하면 좋을까요?
우선 키를 획득하지않고 대문자를 방문했을때를 생각해보면 왔었지만 키가 없을때 소문자를 찾을때까지
다시돌아가는게아니라
소문자를 방문했을때 대문자를 방문했었는지 확인후 그방문했던곳만 다시 꺼내면 해결되지 않을까요?
그렇다면 굳이 방문했던것을 다시 셋팅할 필요가 없어지기때문에 문제느 해결됩니다.
소스코드 :
|
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
|
#include<bits/stdc++.h>
using namespace std;
#define v vector
#define vc v<char>
#define vvc v<vc>
int n, m;
vvc board;
string s;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
board = vvc(n + 2, vc(m + 2, '.'));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
}
}
cin >> s;
}
bool isrange(int y, int x) {
return 0 <= y && y < n + 2 && 0 <= x && x < m + 2;
}
void solve() {
int key = 0;
for (char c : s)
if (c != '0')key |= 1 << (c - 'a');
vvc check(n + 2, vc(m + 2));
queue<pair<int, int>> q, refind[26];
q.push({ 0,0 });
check[0][0] = 1;
int res = 0;
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && check[ny][nx]==0) {
if (board[ny][nx] == '*')continue;
if ('a' <= board[ny][nx] && board[ny][nx] <= 'z') {
key |= 1 << (board[ny][nx] - 'a');
while (!refind[board[ny][nx] - 'a'].empty()) {
q.push(refind[board[ny][nx] - 'a'].front());
check[refind[board[ny][nx] - 'a'].front().first][refind[board[ny][nx] - 'a'].front().second] = 1;
refind[board[ny][nx] - 'a'].pop();
}
}
else if ('A' <= board[ny][nx] && board[ny][nx] <= 'Z') {
if (!(key & 1 << (board[ny][nx] - 'A'))) {
refind[board[ny][nx] - 'A'].push({ ny,nx });
continue;
}
}
else if (board[ny][nx] == '$') {
res++;
board[ny][nx] = '.';
}
q.push({ ny,nx });
check[ny][nx] = 1;
}
}
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
int test;
cin >> test;
while (test--) {
input();
solve();
}
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.