BFS (2)

https://www.acmicpc.net/problem/13913
숨바꼭질 4

#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;
}

https://www.acmicpc.net/problem/9019
DSLR

#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;
}

https://www.acmicpc.net/problem/1525
퍼즐
map 사용

#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;
}

https://www.acmicpc.net/problem/9376
탈옥

#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;
}

https://www.acmicpc.net/problem/9328
열쇠

#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;
}

https://www.acmicpc.net/problem/4991
로봇 청소기

#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;
}

https://www.acmicpc.net/problem/6087
레이저 통신

#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;
}

https://www.acmicpc.net/problem/8111
0과 1

#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;
}