codeplus 백준 강사 강의 내용기반으로 정리한 내용입니다.(비공개 포스트)
덱 사용하기
덱 - 양쪽에서 푸쉬, 팝 가능
숨바꼭질3 문제
BFS는 모든 가중치가 1일 때 풀 수 있는 이유는 시작점에서 거리가 1인 것 다 넣어주고, 다음 거리가 1인거 다 넣어주면 거리1, 거리2인 것 모두 넣어짐
단계별로 나누어지니까 되는데 거리 0이 섞이면 성질을 만족하지 못하는 경우가 나올 수 있음
거리가 2 차이나는 것도 BFS 로 갱신 못함
-> 큐를 두개로 나누어서 처리 가능
0초에서 있는거 다 방문하고 끝나면 1초 큐로 넘어가고 쭉 이어나감
큐를 cur, next 큐 두개 두어 cur 이 비면 교체해주는 방식
-> 덱을 이용해 쉽게 구현가능
#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
bool check[100001];
int dst[100001];
int main()
{
int N = 0;
int K = 0;
const int MAX = 100001;
cin >> N >> K;
memset(check, false, sizeof(check));
memset(dst, -1, sizeof(dst));
check[N] = true;
dst[N] = 0;
deque<int> q;
q.push_front(N);
while (!q.empty()) {
int cur = q.front(); q.pop_front();
if (cur * 2 < MAX) {
if (check[cur * 2] == false) {
dst[cur * 2] = dst[cur];
check[cur * 2] = true;
q.push_front(cur * 2);
}
}
if (cur - 1 >= 0) {
if (check[cur - 1] == false) {
dst[cur - 1] = dst[cur] + 1;
check[cur - 1] = true;
q.push_back(cur - 1);
}
}
if (cur + 1 < MAX) {
if (check[cur + 1] == false) {
dst[cur + 1] = dst[cur] + 1;
check[cur + 1] = true;
q.push_back(cur + 1);
}
}
}
cout << dst[K] << '\n';
return 0;
}
-> 가중치 0은 맨위에 적용시키기(0으로도 갈수있는데 1먼저 가면 최소가 아님)
알고스팟 문제
#include <iostream>
#include <vector>
#include <deque>
#include <cstdio>
using namespace std;
struct Point {
int x;
int y;
Point(int a, int b) : x(a), y(b) {}
};
int main()
{
int N = 0;
int M = 0;
cin >> M >> N;
vector<vector<int>> miro(N+1, vector<int>(M+1, 0));
vector<vector<int>> dst(N+1, vector<int>(M+1, -1));
int dx[4] = {-1,1,0,0};
int dy[4] = { 0,0,-1,1 };
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
scanf_s("%1d", &miro[i][j]);
}
}
deque<Point> q;
q.push_front(Point(0, 0));
dst[0][0] = 0;
while (!q.empty()) {
Point cur = q.front();
q.pop_front();
for (int k = 0; k < 4; ++k) {
if (cur.x + dx[k] >= 0 && cur.x + dx[k] < N && cur.y + dy[k] >= 0 && cur.y + dy[k] < M) {
if (dst[cur.x + dx[k]][cur.y + dy[k]] == -1){
if (miro[cur.x + dx[k]][cur.y + dy[k]] == 0) {
dst[cur.x + dx[k]][cur.y + dy[k]] = dst[cur.x][cur.y];
q.push_front(Point(cur.x + dx[k], cur.y + dy[k]));
} else {
dst[cur.x + dx[k]][cur.y + dy[k]] = dst[cur.x][cur.y] + 1;
q.push_back(Point(cur.x + dx[k], cur.y + dy[k]));
}
}
}
}
}
printf("%d\n", dst[N-1][M-1]);
return 0;
}