# BFS (2)

interviewsangu·2020년 8월 2일
0

## 알고리즘

목록 보기
11/12
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
void go(int now, vector<pair<int, int>>& q) {
if (q[now].first == 0) {
cout << now << ' ';
return;
}
go(q[now].second, q);
cout << now << ' ';
return;
}
int main() {
int n, k;
cin >> n >> k;
vector<pair<int,int>> sec_prev(100001);
vector<bool> check(100001);
queue<int> buf;
sec_prev[n] = make_pair(0, 0);
check[n] = true;
buf.push(n);
while (!buf.empty()) {
int x = buf.front();
if (x == k) break;
buf.pop();
int nx = 2 * x;
if (nx <= 100000 && check[nx] == false) {
check[nx] = true;
sec_prev[nx] = make_pair(sec_prev[x].first + 1, x);
buf.push(nx);
}
nx = x + 1;
if (nx <= 100000 && check[nx] == false) {
check[nx] = true;
sec_prev[nx] = make_pair(sec_prev[x].first + 1, x);
buf.push(nx);
}
nx = x - 1;
if (0 <= nx && check[nx] == false) {
check[nx] = true;
sec_prev[nx] = make_pair(sec_prev[x].first + 1, x);
buf.push(nx);
}
}
cout << sec_prev[k].first << '\n';
go(k, sec_prev);
return 0;
}
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<bool> check(10000);
vector<int> from(10000);
vector<char> how(10000);
check[n] = true;
from[n] = -1;
queue<int> q;
q.push(n);
while (!q.empty()) {
int now = q.front();
q.pop();
int next = (now * 2) % 10000;
if (check[next] == false) {
q.push(next);
check[next] = true;
from[next] = now;
how[next] = 'D';
}
next = now - 1;
if (next == -1) next = 9999;
if (check[next] == false) {
q.push(next);
check[next] = true;
from[next] = now;
how[next] = 'S';
}
next = (now % 1000) * 10 + now / 1000;
if (check[next] == false) {
q.push(next);
check[next] = true;
from[next] = now;
how[next] = 'L';
}
next = (now / 10) + (now % 10) * 1000;
if (check[next] == false) {
q.push(next);
check[next] = true;
from[next] = now;
how[next] = 'R';
}
}
string ans = "";
while (m != n) {
ans += how[m];
m = from[m];
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
return 0;
}
#include <iostream>
#include <queue>
#include <string>
#include <map>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main() {
int n = 3;
int start = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int temp;
cin >> temp;
if (temp == 0) temp = 9;
start = start * 10 + temp;
}
}
queue<int> q;
map<int, int> dist;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int now_num = q.front();
string now = to_string(now_num);
q.pop();
int z = now.find('9');
int x = z / 3;
int y = z % 3;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= n)
continue;
string next = now;
swap(next[x * 3 + y], next[nx * 3 + ny]);
int num = stoi(next);
if (dist.count(num) == 0) {
dist[num] = dist[now_num] + 1;
q.push(num);
}

}
}
if (dist.count(123456789) == 0) {
cout << -1 << '\n';
}
else {
cout << dist[123456789] << '\n';
}
return 0;
}

https://www.acmicpc.net/problem/2251
물통
큐에 pair 가능

#include <iostream>
#include <queue>
using namespace std;
bool ans[201];
bool check[201][201];
int from[] = { 0, 0, 1, 1, 2, 2 };
int to[] = { 1, 2, 0, 2, 0, 1 };
int main() {
int cap[3];
cin >> cap[0] >> cap[1] >> cap[2];
int sum = cap[2];
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
check[0][0] = true;
ans[cap[2]] = true;
while (!q.empty()) {
int cur[3];
cur[0] = q.front().first;
cur[1] = q.front().second;
cur[2] = sum - cur[1] - cur[0];
q.pop();
for (int i = 0; i < 6; i++) {
int next[3] = { cur[0], cur[1],cur[2] };
next[to[i]] += next[from[i]];
next[from[i]] = 0;
if (next[to[i]] >= cap[to[i]]) {
next[from[i]] = next[to[i]] - cap[to[i]];
next[to[i]] = cap[to[i]];
}
if (!check[next[0]][next[1]]) {
check[next[0]][next[1]] = true;
q.push(make_pair(next[0], next[1]));
if (next[0] == 0) ans[next[2]] = true;
}
}
}
for (int i = 0; i <= cap[2]; i++) {
if (ans[i]) cout << i << ' ';
}
cout << '\n';
return 0;
}
#include <iostream>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int main() {
int a, b, c;
cin >> a;
cin >> b;
cin >> c;
map<int, int> m;
queue<int> q;
vector<bool> ans(201);
int to_m = 0;
m[to_m] = 1;
q.push(to_m);
while (!q.empty()) {
int to = q.front();
int cup_a = to / 1000;
int cup_b = to % 1000;
int cup_c = c - cup_a - cup_b;
if (cup_a == 0) {
ans[cup_c] = true;
}
q.pop();
int na, nb, nc, nt;
if (cup_a != 0) {
nc = cup_c;
nb = cup_a + cup_b;
na = 0;
if (nb > b) {
na = nb - b;
nb = b;
}
nt = (na * 1000) + nb;
if (m.count(nt) == 0) {
m[nt] = 1;
q.push(nt);
}
nb = cup_b;
nc = cup_a + cup_b;
na = 0;
if (nc > c) {
na = nc - c;
nc = c;
}
nt = (na * 1000) + nb;
if (m.count(nt) == 0) {
m[nt] = 1;
q.push(nt);
}
}
if (cup_b != 0) {
na = cup_a;
nc = cup_b + cup_c;
nb = 0;
if (nc > c) {
nb = nc - c;
nc = c;
}
nt = (na * 1000) + nb;
if (m.count(nt) == 0) {
m[nt] = 1;
q.push(nt);
}
nc = cup_c;
na = cup_a + cup_b;
nb = 0;
if (na > a) {
nb = na - a;
na = a;
}
nt = (na * 1000) + nb;
if (m.count(nt) == 0) {
m[nt] = 1;
q.push(nt);
}
}
if (cup_c != 0) {
na = cup_a;
nb = cup_b + cup_c;
nc = 0;
if (nb > b) {
nc = nb - b;
nb = b;
}
nt = (na * 1000) + nb;
if (m.count(nt) == 0) {
m[nt] = 1;
q.push(nt);
}
nb = cup_b;
na = cup_a + cup_c;
nc = 0;
if (na > a) {
nc = na - a;
na = a;
}
nt = (na * 1000) + nb;
if (m.count(nt) == 0) {
m[nt] = 1;
q.push(nt);
}
}
}
for (int i = 0; i <= c; i++) {
if (ans[i]) cout << i << ' ';
}
cout << '\n';
return 0;
}

https://www.acmicpc.net/problem/12851
숨바꼭질 2
다이나믹과 BFS가 섞일 수도 있다.
방법의 수 -> 오염되면 안되고, 방법의 수 만 늘려줘야 한다.(다이나믹)
100까지 가는 방법의 수는 100으로 올 수 있는 모든 길들을 더하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool check[100001];
int dist[100001];
int cnt[100001];
int main() {
int n, k;
cin >> n >> k;
queue<int> q;
check[n] = true;
dist[n] = 0;
cnt[n] = 1;
q.push(n);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int next : {now - 1, now + 1, now * 2}) {
if (next < 0 || 100000 < next) continue;
if (check[next] == false) {
check[next] = true;
dist[next] = dist[now] + 1;
cnt[next] += cnt[now];
q.push(next);
}
else if (dist[next] == dist[now] + 1) {
cnt[next] += cnt[now];
}
}
}
cout << dist[k] << '\n';
cout << cnt[k] << '\n';
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
vector<vector<int>> bfs(int x, int y, vector<string>& a) {
int h = a.size();
int w = a[0].size();
vector<vector<int>> d(h, vector<int>(w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
d[i][j] = -1;
}
}
deque<pair<int, int>> q;
d[x][y] = 0;
q.push_back(make_pair(x, y));
while (!q.empty()) {
x = q.front().first; y = q.front().second;
q.pop_front();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
if (d[nx][ny] != -1) continue;
if (a[nx][ny] == '*') continue;
if (a[nx][ny] == '#') {
d[nx][ny] = d[x][y] + 1;
q.push_back(make_pair(nx, ny));
}
else {
d[nx][ny] = d[x][y];
q.push_front(make_pair(nx, ny));
}
}
}
return d;
}
int main() {
int t;
cin >> t;
while (t--) {
int h, w;
cin >> h >> w;
h += 2; w += 2;
vector<string> a(h);
for (int i = 1; i < h - 1; i++) {
cin >> a[i];
a[i] = "." + a[i] + ".";
}
for (int j = 0; j < w; j++) {
a[0] += ".";
a[h - 1] += ".";
}
vector<vector<int>> d0 = bfs(0, 0, a);
int x1, x2, y1, y2;
x1 = -1;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (a[i][j] == '$') { if (x1 == -1) { x1 = i; y1 = j; } else { x2 = i; y2 = j; } } } } vector<vector<int>> d1 = bfs(x1, y1, a); vector<vector<int>> d2 = bfs(x2, y2, a); int ans = h * w; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (a[i][j] == '*') continue; int cur = d0[i][j] + d1[i][j] + d2[i][j]; if (a[i][j] == '#') cur -= 2; if (cur < ans) ans = cur; } } cout << ans << '\n'; } return 0; } #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <string> using namespace std; bool check[101][101]; bool key[26]; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int main() { int t; cin >> t; while (t--) { memset(check, false, sizeof(check)); memset(key, false, sizeof(key)); int h, w; cin >> h >> w; h += 2; w += 2; vector<string> a(h); for (int i = 1; i <= h - 2; i++) { cin >> a[i]; a[i] = '.' + a[i] + '.'; } for (int j = 0; j < w; j++) { a[0] += '.'; a[h - 1] += '.'; } string temp; cin >> temp; for (int i = 0; i < temp.size(); i++) { if (temp[i] - 'a' >= 0) { key[temp[i] - 'a'] = true; } } queue<pair<int, int>> q; queue<pair<int, int>> door[26]; check[0][0] = true; q.push(make_pair(0, 0)); int ans = 0; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue; if (check[nx][ny]) continue; char c = a[nx][ny]; if (c == '*') continue; else if (c == '.') { check[nx][ny] = true; q.push(make_pair(nx, ny)); } else if (c == '$') {
ans += 1;
check[nx][ny] = true;
q.push(make_pair(nx, ny));
}
else if (c >= 'a' && c <= 'z') {
check[nx][ny] = true;
q.push(make_pair(nx, ny));
if (!key[c - 'a']) {
key[c - 'a'] = true;
while (!door[c - 'a'].empty()) {
q.push(door[c - 'a'].front());
door[c - 'a'].pop();
}
}
}
else if (c >= 'A' && c <= 'Z') {
if (key[c - 'A']) {
check[nx][ny] = true;
q.push(make_pair(nx, ny));
}
else {
check[nx][ny] = true;
door[c - 'A'].push(make_pair(nx, ny));
}
}
}
}
cout << ans << '\n';
}
return 0;
}
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
vector<vector<int>> bfs(vector<string>& a, int sx, int sy) {
int h = a.size();
int w = a[0].size();
queue<pair<int, int>> q;
vector<vector<int>> dist(h, vector<int>(w, -1));
dist[sx][sy] = 0;
q.push(make_pair(sx, sy));
while (!q.empty()) {
int x = q.front().first; int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || h <= nx || w <= ny) continue;
if (dist[nx][ny] == -1 && a[nx][ny] != 'x') {
dist[nx][ny] = dist[x][y] + 1;
q.push(make_pair(nx, ny));
}
}
}
return dist;
}
int main() {
while (true) {
int w, h;
cin >> w >> h;
if (w == 0 && h == 0) break;
vector<string> a(h);
for (int i = 0; i < h; i++) {
cin >> a[i];
}
vector<pair<int, int>> b(1);
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (a[i][j] == 'o') {
b[0] = make_pair(i, j);
}
else if (a[i][j] == '*') {
b.push_back(make_pair(i, j));
}
}
}
int l = b.size();
vector<vector<int>> d(l, vector<int>(l));
bool ok = true;
for (int i = 0; i < l; i++) {
auto p = bfs(a, b[i].first, b[i].second);
for (int j = 0; j < l; j++) {
d[i][j] = p[b[j].first][b[j].second];
if (d[i][j] == -1) {
ok = false;
}
}
}
if (!ok) {
cout << -1 << '\n';
continue;
}
int ans = -1;
vector<int> p(l - 1);
for (int i = 0; i < l - 1; i++) {
p[i] = i + 1;
}
do {
int now = d[0][p[0]];
for (int k = 0; k < l - 2; k++) {
now += d[p[k]][p[k + 1]];
}
if (ans == -1 || now < ans) {
ans = now;
}
} while (next_permutation(p.begin(), p.end()));
cout << ans << '\n';
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <tuple>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main() {
int w, h;
cin >> w >> h;
vector<string> a(h);
for (int i = 0; i < h; i++) {
cin >> a[i];
}
int sx = -1, sy = -1, ex = -1, ey = -1;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (a[i][j] == 'C') {
if (sx == -1) {
sx = i;
sy = j;
}
else {
ex = i;
ey = j;
}
}
}
}
vector<vector<int>> dist(h, vector<int>(w, -2));
queue<pair<int, int>> q;
q.push(make_pair(sx, sy));
dist[sx][sy] = -1;
while (!q.empty()) {
int x = q.front().first; int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
while (0 <= nx && 0 <= ny && nx < h && ny < w) {
if (a[nx][ny] == '*') break;
if (dist[nx][ny] == -2) {
dist[nx][ny] = dist[x][y] + 1;
q.push(make_pair(nx, ny));
}
nx += dx[k];
ny += dy[k];
}
}
}
cout << dist[ex][ey] << '\n';
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <tuple>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n == 1) {
cout << 1 << '\n';
continue;
}
vector<int> from(n, -1);
vector<int> how(n, -1);
queue<int> q;
how[1] = 1;
q.push(1);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i <= 1; i++) {
int next = (now * 10 + i) % n;
if (how[next] == -1) {
how[next] = i;
from[next] = now;
q.push(next);
}
}
}
string ans = "";
for (int i = 0; i != -1; i = from[i]) {
ans = ans + to_string(how[i]);
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
return 0;
}