(C++) [백준 9328번] 열쇠
https://www.acmicpc.net/problem/9328
9328번: 열쇠
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가
www.acmicpc.net
예전보다 어려운 난이도의 BFS 문제를 풀 수 있게 된건 좋은데, 맞다 싶으면 무조건 제출하고 보는 경향 때문에 자꾸만 정답률이 낮아지는게 신경쓰인다.
엄청난 틀렸습니다를 보고야 깨달은거지만, 이 다음 문제부터는 예제만 맞다고 무조건 내고 보지 말고 자체 디버깅이나 다양한 반례를 만들어보고 내는 습관을 가져야겠다고 생각했다...
다른 BFS 문제(특히 불!이나 불:https://www.acmicpc.net/problem/5427) 처럼 2차원 배열이 주어지고, 상하좌우로 한 칸씩 이동한다던가 하는 조건이 있다면 BFS 문제겠구나 하는걸 점점 깨닫게 되는 것 같다.
이 문제는 건물의 1층이라는 조건이 있으므로 3차원 배열은 아니고, 2차원 배열 내에서 가장 많이 훔칠 수 있는 문서의 개수를 출력하는 문제이다.
문제 설명을 보면 '*'는 벽, '.'은 길, '$'은 문서, 'a~z'는 열쇠, 'A~Z'는 문이다. 소문자 알파벳 열쇠를 획득하면 그 알파벳에 대응하는 대문자 알파벳 문을 열 수 있게 된다. BFS를 통해 얻을 수 있는 문서의 개수를 찾으면 된다.
처음에 BFS를 연습하기 시작했을 때는 단순히 visited 배열이나 board 배열 자체에 거리값을 줌으로써 한 시작점에 대해서 한 번씩만 탐색하면 되는 문제들이 많아서 수월했는데, 요즘 문제를 풀다 보면 한 시작점에 대해서 여러 번 탐색해야 하는 경우가 많아서 좀 어렵다고 느낀다. 어떻게 푸는게 정해인지 아직도 잘 모르겠다.
우선 내가 처음 생각했던 방법은 다음과 같다.
1. 2중 for문 맨 안쪽에 시작점으로 들어올 수 있는지 확인하는 isOpen(i,j) 함수를 통해 시작점으로 올 수 있는 점이 있다면
큐에 push하고, while(cnt > 0) 안에 while(!q.empty())를 넣고, 열쇠를 찾았을 경우에 cnt를 증가시켜서 열쇠를 못 찾을때까지 계속 while문을 돌린다.
2. while문이 끝나면 찾은 문서의 개수를 리턴한다.
였는데 제대로 나오질 않더라. 예제는 통과했는데 계속 틀렸습니다를 받아서, 답답해서 찾아보니까 채점 데이터가 있더라. 넣어보니까 당연히 틀린걸 발견했고 코드보다는 논리부터 틀린 것 같아서 수정에 들어갔다.
처음 정답을 받았을 때 생각했던 방법은 다음과 같았다.
1. 처음 생각했던 방법에서 while(true)를 맨 바깥쪽에 추가하고, 이 while문을 종료시키기 위한 k를 만들어서 열쇠를 찾으면 cnt와 k를 같이 증가시키고, k가 0이면 종료하고( = 열쇠를 못 찾으면) 이때까지 찾은 문서의 개수를 리턴한다.
였는데, 정답을 받긴 받았다. 아래는 처음 AC받은 코드이다.
|
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second
#define MAX 102
char board[MAX][MAX];
bool vis[MAX][MAX], docu[MAX][MAX],door[26];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue <pair<int, int>> q;
queue <pair<int, int>> sub;
int w, h, t;
string str;
void input()
{
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
docu[i][j] = false;
board[i][j] = '*';
}
}
for (int i = 0; i < 26; i++)
door[i] = false;
while (!q.empty()) q.pop();
cin >> h >> w;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> board[i][j];
}
}
cin >> str;
if (str[0] == '0') return;
int len = str.length();
for (auto i : str)
door[i - 'a'] = true;
}
bool isOpen(int i,int j)
{
if (board[i][j] >= 'A' && board[i][j] <= 'Z')
if (!door[board[i][j] - 'A']) return false;
if (board[i][j] == '*') return false;
if (i == 0 || j == 0 || i == h - 1 || j == w - 1) return true;
return false;
}
int solve()
{
int res = 0;
int cnt = 0, t = 0;
while (true)
{
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
while (true)
{
if (isOpen(i, j))
{
q.push({ i,j });
vis[i][j] = true;
if (board[i][j] >= 'a' && board[i][j] <= 'z')
door[board[i][j] - 'a'] = true;
if (board[i][j] == '$')
{
if (!docu[i][j]) {
res++;
docu[i][j] = true;
}
}
}
while (!q.empty())
{
auto cur = q.front(); q.pop();
int x = cur.X;
int y = cur.Y;
for (int dir = 0; dir < 4; dir++)
{
int nx = dx[dir] + cur.X;
int ny = dy[dir] + cur.Y;
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (vis[nx][ny] || board[nx][ny] == '*') continue;
if (board[nx][ny] == '.')
{
q.push({ nx,ny });
vis[nx][ny] = true;
}
if (board[nx][ny] == '$')
{
if (!docu[nx][ny]) // 아직 방문하지 않은 문서라면(얻을 수 있는 문서)
{
res++;
docu[nx][ny] = true;
}q.push({ nx,ny });
vis[nx][ny] = true;
}
if (board[nx][ny] >= 'A' && board[nx][ny] <= 'Z') // 문이라면
{
if (door[board[nx][ny] - 'A']) // 열 수 있는 문이라면
{
q.push({ nx,ny });
vis[nx][ny] = true;
}
}
if (board[nx][ny] >= 'a' && board[nx][ny] <= 'z') // 열쇠라면
{
if (!door[board[nx][ny] - 'a'])
{
cnt++;
t++;
}door[board[nx][ny] - 'a'] = true;
q.push({ nx,ny });
vis[nx][ny] = true;
}
}
}
for (int i = 0; i < MAX; i++)
fill(vis[i], vis[i] + MAX, false); // 방문한 점 초기화
if (cnt == 0)
break;
cnt = 0;
}
}
}
if (t == 0) break;
t = 0;
}
return res;
}
int main()
{
cin.tie(0); ios::sync_with_stdio(0);
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
input(); cout << solve() << "\n";
}
}
|
cs |
보면 56번째에 가장 바깥쪽에 while(true)가 있고, 가장 안쪽 62번째 줄에 while(true)가 있는데 2중 for문의 j번째 시작점에서 열쇠를 찾았는지 확인하는게 62번째줄 while문이고, 2중 for문을 h*w번 돌렸을때 열쇠를 찾았는지 확인하는게 56번째줄 while문이다.
이 두 while문이 모두 종료된다는 것은 2중 for문을 O(hw)번 돌렸을 때 열쇠가 하나도 없다는 것이고, 2중 for문을 O(hw)번 돌리고 열쇠가 없다면 더이상 갈 수 있는 곳이 없다고 판단해서 종료시켰고, AC를 받긴 했다.. 그런데
풀긴 했는데 기분도 영 찝찝하고, 다른 BFS에서도 이런 경우가 종종 있었어서 이번에는 시간도 좀 빠르게 개선해봐야겠다 싶더라.
다른분들 코드도 열심히 참고하고 수정하고 하다가 결국 개선할 수 있는 곳을 발견해서 개선하긴 했다.
두 가지 정도의 개선점을 발견할 수 있었다.
첫번째로는 아까 코드에서 62번째 줄에 해당하는 while문이었는데, 처음 이 while문을 작성했던 의도는 한 시작점에 대해 여러번 BFS를 돌려야한다고 생각했기 때문이다.
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz위와 같은 입력에 대해서 (1,0)이 시작점으로 들어가면, BFS를 1번 수행하면 찾을 수 있는 열쇠의 개수는 'p' 1개일거라 생각했고, 그래서 한 시작점에 대해서 열쇠를 찾지 못할때까지 계속해서 BFS를 돌려야겠다고 생각했다. 그런데, 로직을 다시 생각해보니까 56번째 줄의 while문이 있으면 필요가 없는 while문이었다. 어차피 첫 BFS에서 열쇠를 1개라도 찾으면
56번째 줄의 가장 바깥쪽 while문이 다시 2중 for문을 수행할거고, 그렇게 되면 새로운 열쇠를 찾으니까 외부 while문만 남겨도 상관없었다.
두번째는 첫번째 개선점과도 연관되는데, 62번째 줄의 가장 안쪽 while문이 필요없어지니까 while(!q.empty())가 끝날 때마다 수행되는 124번째 줄의 vis를 초기화시키는 for문도 필요가 없어졌다. 이 for문은 한번 큐에 들어간 점들이 끝나고 나면 다시 방문할 수 없는 점들을 방문하게 만들어주는 코드였는데, 이 코드도 어차피 BFS를 한 번만 수행하도록 바뀌면서 56번째 줄의 가장 바깥쪽 while문으로 뺄 수 있었다.
|
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second
#define MAX 102
char board[MAX][MAX];
bool vis[MAX][MAX],door[26];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue <pair<int, int>> q;
queue <pair<int, int>> sub;
int w, h, t;
string str;
void input()
{
for (int i = 0; i < MAX; i++)
{
fill(vis[i], vis[i] + MAX, false); // 방문한 점 초기화
fill(board[i], board[i] + MAX, '*');
}
for (int i = 0; i < 26; i++)
door[i] = false;
while (!q.empty()) q.pop();
cin >> h >> w;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> board[i][j];
}
}
cin >> str;
if (str[0] == '0') return;
int len = str.length();
for (auto i : str)
door[i - 'a'] = true;
}
bool isOpen(int i,int j)
{
if (board[i][j] >= 'A' && board[i][j] <= 'Z')
if (!door[board[i][j] - 'A']) return false;
if (board[i][j] == '*') return false;
if (i == 0 || j == 0 || i == h - 1 || j == w - 1) return true;
return false;
}
int solve()
{
int res = 0;
int cnt = 1, t = 1;
while (t != 0)
{
t = 0;
for (int i = 0; i < MAX; i++)
fill(vis[i], vis[i] + MAX, false); // 방문한 점 초기화
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (isOpen(i, j))
{
q.push({ i,j });
vis[i][j] = true;
if (board[i][j] >= 'a' && board[i][j] <= 'z')
door[board[i][j] - 'a'] = true;
if (board[i][j] == '$')
{
res++;
board[i][j] = '.';
}
}
while (!q.empty())
{
auto cur = q.front(); q.pop();
int x = cur.X;
int y = cur.Y;
for (int dir = 0; dir < 4; dir++)
{
int nx = dx[dir] + cur.X;
int ny = dy[dir] + cur.Y;
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (vis[nx][ny] || board[nx][ny] == '*') continue;
if (board[nx][ny] == '.')
{
q.push({ nx,ny });
vis[nx][ny] = true;
}
else if (board[nx][ny] == '$')
{
res++;
board[nx][ny] = '.';
q.push({ nx,ny });
vis[nx][ny] = true;
}
else if (board[nx][ny] >= 'A' && board[nx][ny] <= 'Z') // 문이라면
{
if (door[board[nx][ny] - 'A']) // 열 수 있는 문이라면
{
q.push({ nx,ny });
vis[nx][ny] = true;
}
}
else if (board[nx][ny] >= 'a' && board[nx][ny] <= 'z') // 열쇠라면
{
t++;
door[board[nx][ny] - 'a'] = true;
q.push({ nx,ny });
vis[nx][ny] = true;
board[nx][ny] = '.';
}
}
}
}
}
}
return res;
}
int main()
{
cin.tie(0); ios::sync_with_stdio(0);
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
input(); cout << solve() << "\n";
}
}
|
cs |
최종적으로 제출하고 8ms의 시간만에 통과된 코드는 위의 코드이다.
첫 코드에서 62번째줄에 해당하던 while문을 빼고, 문서를 획득했는지 확인하던 docu배열도 빼버렸다. docu배열은 문서를 획득하면 '$'을 '.'으로 바꿈으로써 해결했다. 124번째줄의 vis 초기화도 바깥쪽 while문으로 이동시키면서 시간을 꽤 단축했다.
이번 문제를 풀면서 여러가지를 배운 것 같다.
특히, 예제만 맞다고 무작정 제출하고 보거나, 시간이 오래 걸리더라도 일단 제출한다거나, 깊은 고민 없이 코드를 짠다거나..하는 행동은 정말 지양해야 할 것 같다. 또 BFS를 돌릴때 무작정 한 시작점에 대해서 여러번 탐색하지 말고 외부 while문을 이용하는 방법이 좋은 것 같다.
