BFS

• BFS는 임의의 시작 점에서 모든 정점을 한번씩 방문하는 알고리즘이다.

• 최단 거리를 구하는 알고리즘이기도 하다.

• BFS를 이용해 해결할 수 있는 최단 거리 문제는 다음과 같은 조건들을 만족해야 한다.
  (1) 최소 비용 문제
  (2) 간선의 가중치는 모두 1
  (3) 정점과 간선의 개수가 적당히 적어야 한다.

• 간선에 1이 아닌 가중치가 주어진 경우, 특정 간선의 사용 횟수 제한이 있는 경우 주의

https://www.acmicpc.net/problem/2178
미로 탐색

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int check[100][100];
int dist[100][100];
int dy[] = { 1, -1, 0, 0 };
int dx[] = { 0, 0, 1, -1 };
int n, m;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	check[y][x] = 0;
	dist[y][x] = 1;
	q.push(make_pair(y, x));
	while (!q.empty()) {
		pair<int, int> now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = now.first + dy[i];
			int nx = now.second + dx[i];
			if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
			if (check[ny][nx] == 1) {
				q.push(make_pair(ny, nx));
				check[ny][nx] = 0;
				dist[ny][nx] = dist[now.first][now.second] + 1;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &check[i][j]);
		}
	}
	bfs(0, 0);
	cout << dist[n - 1][m - 1] << '\n';
	return 0;
}

https://www.acmicpc.net/problem/7576
토마토
시작점이 여러개인 경우 모두 큐에 쳐 넣으면 됨, 알아서 여러 시작점에서 순차적으로 시작

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int check[1000][1000];
int dist[1000][1000];
int dy[] = { 1, -1, 0, 0 };
int dx[] = { 0, 0, 1, -1 };
int main() {
	int n, m;
	cin >> m >> n;
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> check[i][j];
			if (check[i][j] == 1) {
				q.push(make_pair(i, j));
				dist[i][j] = 0;
			}
		}
	}
	while (!q.empty()) {
		pair<int, int> now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = now.first + dy[i];
			int nx = now.second + dx[i];
			if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
			if (check[ny][nx] == 0) {
				q.push(make_pair(ny, nx));
				check[ny][nx] = 1;
				dist[ny][nx] = dist[now.first][now.second] + 1;
			}
		}
	}
	bool zero = false;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (ans < dist[i][j]) ans = dist[i][j];
			if (check[i][j] == 0) zero = true;
		}
	}
	if (zero) cout << -1 << '\n';
	else cout << ans << '\n';
	return 0;
}

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

런타임 에러 나온 이유 : next 범위 확인 안함, 끝자리 확인 주의

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int sec[100001];
int main() {
	memset(sec, -1, sizeof(sec));
	int n, k;
	cin >> n >> k;
	if (n == k) {
		cout << 0 << '\n';
		return 0;
	}
	queue<int> q;
	sec[n] = 0;
	q.push(n);
	while (!q.empty()) {
		int now = q.front();
		if (now == k) break;
		q.pop();
		int next;
		next = now + 1;
		if (next <100001 && sec[next] == -1) {
			sec[next] = sec[now] + 1;
			q.push(next);
		}
		next = now - 1;
		if (next >= 0 && sec[next] == -1) {
			sec[next] = sec[now] + 1;
			q.push(next);
		}
		next = now * 2;
		if (next < 100001 && sec[next] == -1) {
			sec[next] = sec[now] + 1;
			q.push(next);
		}
	}
	cout << sec[k] << '\n';
	return 0;
}

https://www.acmicpc.net/problem/14226
이모티콘

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int sec[1001][1001];
int main() {
	memset(sec, -1, sizeof(sec));
	int s;
	cin >> s;
	queue<pair<int, int>> q;
	sec[1][0] = 0;
	q.push(make_pair(1, 0));
	while (!q.empty()) {
		int now = q.front().first;
		if (now == s) break;
		int copy = q.front().second;
		q.pop();
		if (sec[now][now] == -1) {
			sec[now][now] = sec[now][copy] + 1;
			q.push(make_pair(now, now));
		}
		if (sec[now + copy][copy] == -1 && copy != 0
			&& now + copy <= 1000) {
			sec[now + copy][copy] = sec[now][copy] + 1;
			q.push(make_pair(now + copy, copy));
		}
		if (sec[now - 1][copy] == -1 && now - 1 >= 0) {
			sec[now - 1][copy] = sec[now][copy] + 1;
			q.push(make_pair(now - 1, copy));
		}
	}
	cout << sec[q.front().first][q.front().second] << '\n';
	return 0;
}

덱 사용하기

https://www.acmicpc.net/problem/13549
숨바꼭질 3
시간초가 적은 것들이 먼저 큐에 들어가게 해야 한다.
&& 연산에서 범위가 먼저 검색되게 해야 한다

큐로 풀 때 순서에 의해서 바뀐다고??? -> 그냥 덱으로 풀자
n = 1일 때 어디로 순서가 바뀔 수 있어서 그런가?

#include <iostream>
#include <queue>
#include <deque>
using namespace std;
bool c[1000000];
int d[1000000];
int MAX = 1000000;
int main() {
    int n, m;
    cin >> n >> m;
    c[n] = true;
    d[n] = 0;
    deque<int> q;
    q.push_back(n);
    while (!q.empty()) {
        int now = q.front();
        q.pop_front();
        if (now+1 < MAX) {
            if (c[now+1] == false && (now + 1) != 2) {
                q.push_back(now+1);
                c[now+1] = true;
                d[now+1] = d[now] + 1;
            }
        }
        if (now*2 < MAX) {
            if (c[now*2] == false) {
                q.push_front(now*2);
                c[now*2] = true;
                d[now*2] = d[now];
            }
        }
        if (now-1 >= 0) {
            if (c[now-1] == false) {
                q.push_back(now-1);
                c[now-1] = true;
                d[now-1] = d[now] + 1;
            }
        }
    }
    cout << d[m] << '\n';
    return 0;
}

https://www.acmicpc.net/problem/1261
알고스팟

벽을 최소로 뚫고 나가야하기 때문에 벽을 깨부순 개수로 나눠야 한다
큐를 새로 만들거나 덱을 사용한다.

#include <cstdio>
#include <queue>
using namespace std;
int d[555][555];
int a[555][555];
int n,m;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main() {
    scanf("%d %d",&m,&n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%1d",&a[i][j]);
            d[i][j] = -1;
        }
    }
    queue<pair<int,int>> q;
    queue<pair<int,int>> next_queue;
    q.push(make_pair(0,0));
    d[0][0] = 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 (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (d[nx][ny] == -1) {
                    if (a[nx][ny] == 0) {
                        d[nx][ny] = d[x][y];
                        q.push(make_pair(nx,ny));
                    } else {
                        d[nx][ny] = d[x][y]+1;
                        next_queue.push(make_pair(nx,ny));
                    }
                }
            }
        }
        if (q.empty()) {
            q = next_queue;
            next_queue = queue<pair<int,int>>();
        }
    }
    printf("%d\n",d[n-1][m-1]);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int room[101][101];
int cnt[101][101];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &room[i][j]);
		}
	}
	deque<pair<int, int>> q;
	cnt[1][1] = 0;
	room[1][1] = -1;
	q.push_back(make_pair(1, 1));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop_front();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny <= 0 || nx <= 0 || ny > n || nx > m) continue;
			if (room[ny][nx] == 0) {
				room[ny][nx] = -1;
				cnt[ny][nx] = cnt[y][x];
				q.push_front(make_pair(ny, nx));
			}
			if (room[ny][nx] == 1) {
				room[ny][nx] = -1;
				cnt[ny][nx] = cnt[y][x] + 1;
				q.push_back(make_pair(ny, nx));
			}
		}
	}
	cout << cnt[n][m] << '\n';
	return 0;
}

https://www.acmicpc.net/problem/2206
벽 부수고 이동하기

이전 문제가 벽을 부수는 개수에 따라 큐를 계속해서 만들어 사용한다면 (예를 들어 벽 0개 큐를 모두 소모하고 벽 1개로 넘어가고 ..) 이 문제는 딱 한번만 부술 수 있다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int room[1001][1001];
int dist[1001][1001][2];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &room[i][j]);
		}
	}
	queue<tuple<int, int, int>> q;
	dist[1][1][0] = 1;
	q.push(make_tuple(1, 1, 0));
	while (!q.empty()) {
		int y, x, z;
		tie(y, x, z) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx <= 0 || ny <= 0 || nx > m || ny > n) continue;
			if (room[ny][nx] == 0 && dist[ny][nx][z] == 0) {
				dist[ny][nx][z] = dist[y][x][z] + 1;
				q.push(make_tuple(ny, nx, z));
			}
			if (z == 0 && room[ny][nx] == 1 && dist[ny][nx][z + 1] == 0) {
				dist[ny][nx][z + 1] = dist[y][x][z] + 1;
				q.push(make_tuple(ny, nx, z + 1));
			}
		}
	}
	if (dist[n][m][0] != 0 && dist[n][m][1] != 0) {
		cout << min(dist[n][m][0], dist[n][m][1]);
	}
	else if (dist[n][m][0] != 0) {
		cout << dist[n][m][0];
	}
	else if (dist[n][m][1] != 0) {
		cout << dist[n][m][1];
	}
	else {
		cout << -1;
	}
	cout << '\n';
	return 0;
}

룸을 바꾸면 안됨, z = 0에서 변경하면 z = 1에서 사용 못함

https://www.acmicpc.net/problem/3055
탈출

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
int water[50][50];
int go[50][50]; 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int main() {
	int r, c;
	cin >> r >> c;
	vector<string> a(r);
	for (int i = 0; i < r; i++) {
		cin >> a[i];
	}
	memset(water, -1, sizeof(water));
	queue<pair<int, int>> q;
	int gx, gy, ex, ey;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (a[i][j] == '*') {
				q.push(make_pair(i, j));
				water[i][j] = 0;
			}
			else if (a[i][j] == 'S') {
				gx = i;
				gy = j;
			}
			else if (a[i][j] == 'D') {
				ex = i;
				ey = 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 >= r || ny < 0 || ny >= c) continue;
			if (water[nx][ny] == -1 && a[nx][ny] == '.') {
				water[nx][ny] = water[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
	memset(go, -1, sizeof(go));
	go[gx][gy] = 0;
	q.push(make_pair(gx, gy));
	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 >= r || ny < 0 || ny >= c) continue;
			if (go[nx][ny] != -1) continue;
			if (a[nx][ny] == 'X') continue;
			if (water[nx][ny] == -1 || go[x][y] + 1 < water[nx][ny]) {
				go[nx][ny] = go[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
	if (go[ex][ey] == -1) {
		cout << "KAKTUS\n";
	}
	else {
		cout << go[ex][ey] << '\n';
	}
	return 0;
}