BFS
DFS와 목적이 동일, 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는것
특징은 DFS와 다르게 최단 거리를 구하는 알고리즘이다. 단 BFS는 모든 가중치가 1이어야만 하고 가중치가 1이 아니면 다익스트라 알고리즘을 이용하게 된다.
문제
1697 숨바꼭질
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
//int d[100001];
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> d(100001, -1);
queue<int> q;
q.push(n);
d[n] = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (cur * 2 <= 100000 && d[cur * 2] == -1)
{
d[cur * 2] = d[cur] + 1;
q.push(cur * 2);
}
if (cur - 1 >= 0 && d[cur - 1] == -1)
{
d[cur - 1] = d[cur] + 1;
q.push(cur - 1);
}
if (cur + 1 <= 100000 && d[cur + 1] == -1
)
{
d[cur + 1] = d[cur] + 1;
q.push(cur + 1);
}
}
cout << d[k] << '\n';
}숨바꼭질 4
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
vector<int> d(100001, -1);
vector<int> p(100001, -1);
void go(int k)
{
if (p[k] == -1)
{
cout << k << ' ';
return ;
}
go(p[k]);
cout << k << ' ';
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
queue<int> q;
q.push(n);
d[n] = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (cur * 2 <= 100000 && d[cur * 2] == -1)
{
d[cur * 2] = d[cur] + 1;
p[cur * 2] = cur;
q.push(cur * 2);
}
if (cur - 1 >= 0 && d[cur - 1] == -1)
{
d[cur - 1] = d[cur] + 1;
p[cur - 1] = cur;
q.push(cur - 1);
}
if (cur + 1 <= 100000 && d[cur + 1] == -1)
{
d[cur + 1] = d[cur] + 1;
p[cur + 1] = cur;
q.push(cur + 1);
}
}
cout << d[k] << '\n';
go(k);
}14502 연구소
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
int a[10][10];
int b[10][10];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int n, m;
int bfs(void)
{
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
b[i][j] = a[i][j];
if (b[i][j] == 2)
q.push(make_pair(i,j));
}
}
while (!q.empty())
{
int x, y;
tie(x, y) = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (b[nx][ny] != 0) continue;
b[nx][ny] = 2;
q.push(make_pair(nx, ny));
}
}
int ans = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (b[i][j] == 0) ans++;
}
}
return (ans);
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> a[i][j];
}
}
int ans = 0;
for (int x1 = 0; x1 < n; ++x1)
{
for (int y1 = 0; y1 < m; ++y1)
{
if (a[x1][y1] != 0) continue;
a[x1][y1] = 1;
for (int x2 = 0; x2 < n; ++x2)
{
for (int y2 = 0; y2 < m; ++y2)
{
if (a[x2][y2] != 0) continue;
if (x1 == x2 && y1 == y2) continue;
a[x2][y2] = 1;
for (int x3 = 0; x3 < n; ++x3)
{
for (int y3 = 0; y3 < m; ++y3)
{
if (a[x3][y3] != 0) continue;
if ((x1 == x3 && y1 == y3) || (x2 == x3 && y2 == y3)) continue;
a[x3][y3] = 1;
int tmp = bfs();
if (ans < tmp) ans = tmp;
a[x3][y3] = 0;
}
}
a[x2][y2] = 0;
}
}
a[x1][y1] = 0;
}
}
cout << ans << '\n';
}17141 연구소2
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
int a[51][51];
int b[51][51];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int n, m;
int ans = -1;
vector<pair<int, int>> pos;
void bfs(void)
{
memset(b, -1, sizeof(b));
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
//바이러스가 놓여진 위치
if (a[i][j] == 3)
{
q.push(make_pair(i, j));
b[i][j] = 0;
}
}
}
//바이러스 돌리기
while (!q.empty())
{
int x, y;
tie(x, y) = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (a[nx][ny] != 1 && b[nx][ny] == -1)
{
b[nx][ny] = b[x][y] + 1;
q.push(make_pair(nx, ny));
}
}
}
}
int cur = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (a[i][j] != 1)
{
if (b[i][j] == -1) return;
if (cur < b[i][j]) cur = b[i][j];
}
}
}
if (ans == -1 || ans > cur) ans = cur;
}
void go(int index, int cnt)
{
if (index == pos.size())
{
if (cnt == m)
{
bfs();
return;
}
}
else {
int i, j;
tie(i, j) = pos[index];
a[i][j] = 3;
go(index + 1, cnt + 1);
a[i][j] = 0;
go(index + 1, cnt);
}
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> a[i][j];
if (a[i][j] == 2)
{
pos.push_back(make_pair(i, j));
a[i][j] = 0;
}
}
}
go(0,0);
cout << ans << '\n';
}17142 연구소 3
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
int a[51][51];
int b[51][51];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int n, m;
int ans = -1;
vector<pair<int, int>> pos;
void bfs(void)
{
memset(b, -1, sizeof(b));
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
//바이러스가 놓여진 위치
if (a[i][j] == 3)
{
q.push(make_pair(i, j));
b[i][j] = 0;
}
}
}
//바이러스 돌리기
while (!q.empty())
{
int x, y;
tie(x, y) = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (a[nx][ny] != 1 && b[nx][ny] == -1)
{
b[nx][ny] = b[x][y] + 1;
q.push(make_pair(nx, ny));
}
}
}
}
int cur = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (a[i][j] == 0)
{
if (b[i][j] == -1) return;
if (cur < b[i][j]) cur = b[i][j];
}
}
}
if (ans == -1 || ans > cur) ans = cur;
}
void go(int index, int cnt)
{
if (index == pos.size())
{
if (cnt == m)
{
bfs();
return;
}
}
else {
int i, j;
tie(i, j) = pos[index];
a[i][j] = 3;
go(index + 1, cnt + 1);
a[i][j] = 2;
go(index + 1, cnt);
}
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> a[i][j];
if (a[i][j] == 2)
{
pos.push_back(make_pair(i, j));
//a[i][j] = 0;
}
}
}
go(0,0);
cout << ans << '\n';
}
신촌거지출신개발자(시리즈 부분에 목차가 나옵니다.)