문제 : https://www.acmicpc.net/problem/2667
깨달은 것
BFS, queue 사용, C++ STL queue vs vector
1. BFS
BFS를 통해 주변을 먼저 탐색 후 그 주변의 주변을 탐색하는 알고리즘이다. DFS는 재귀나 stack을 사용할 수 있는 반면, BFS는 queue를 사용하는 것이 일반적이다.
for (int i = 0; i < 6; i++) //탐색 부분
{
int new_x = curr.x + dx[i];
int new_y = curr.y + dy[i];
int new_z = curr.z + dz[i];
if (inbound(new_x, new_y, new_z) && t[new_z][new_y][new_x] == 0)
{
t[new_z][new_y][new_x] = 1;
q.push(idx {new_x, new_y, new_z, res + 1});
}
}2. queue의 사용
queue를 사용할 때는 탐색하고자 하는 곳들을 insert하는 방식을 갖는다.
"그래서 탐색하고자 하는 지점들을 insert한다"
라는 것을 기억하는 것이 좋을 것 같다고 느꼈다.
for (int i = 0; i < H; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < M; k++)
{
cin >> t[i][j][k];
if (t[i][j][k] == 1)
// 1일시에 q에 push하는 것을 볼 수 있다.
q.push({k, j, i, 0});
else if (t[i][j][k] == 0)
flag = true;
}
}
}예를 들어 다른 BFS문제를 풀때는 pop한 탐색 지점의 주변부들만 insert하는 것으로 생각했지만, 그렇지가 않았다.
전체적으로 탐색하고자 하는 지점들이 많다면 그 지점들을 먼저 insert해주는 방법도 있다는 것을 알아야했다. 아직은 DFS를 할 때 stack에서도 임의로 탐색하고 싶은 지점을 넣을 수 있을지는 더 공부해봐야겠다.
C++ STL vector vs queue
vector로도 queue를 구현을 할 수 있었다. 하지만, 이는 생각보다 비효율적인 행동이었다. queue가 있는데 굳이 vector를 사용할 필요가 있을까. 더군다나 queue가 훨씬 빠르다.
https://cplusplus.com/reference/queue/queue/
https://cplusplus.com/reference/vector/vector/
while (!q.empty())
{
idx curr = q.front();
q.erase(q.begin());
....
vector로 queue를 구현했을 때 vs
while (!q.empty())
{
idx curr = q.front();
q.pop();vector 문서를 참고해보면..
vector는 자유자재로 변할 수 있는 반면 아예 새로운 배열을 할당하는 것을 알 수 있다. 메모리에 연속 된 자리에 array를 할당하려 하니, array의 잦은 메모리 할당으로 시간이 느려질 수 있다는 것이다.
반명 queue는 deque(덱) 이라는 STL을 사용한다. deque은 vector와 다르게 직접 array를 할당하지 않는다. 하지만 array의 요소들이 연속된 자리에 위치하지 않고 분산된 자리에 있기 때문에 "지속된 반복자(consistent reference)"이기엔 어렵다고 한다.
