바킹독알고리즘 블로그 보고 정리한 내용입니다
출처 : https://blog.encrypted.gg/941
[실전 알고리즘] 0x09강 - BFS
안녕하세요 여러분, 드디어 올 것이 왔습니다. 마음의 준비를 단단히 하셔야 합니다.. 드디어 실전 알고리즘 강의에서 첫 번째 고비에 도달했는데 이 강의와 함께 이번 고비를 잘 헤쳐나가면 좋
blog.encrypted.gg
BFS : Breadth First Search
다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
그래프 자료구조에서 모든 노드를 탐색하는 것.
이런 2차원 배열이 있다고 하자
| 0 | 1 | 2 | |
| 0 | (0, 0) | (0, 1) | (0, 2) |
| 1 | (1, 0) | (1, 1) | (1, 2) |
| 2 | (2, 0) | (2, 1) | (2, 2) |
(0, 0)에서 시작할 경우 (상, 하, 좌, 우) 탐색
1. (0, 0) 시작
(0, 0) push
큐 : (0, 0)
2. (1, 0), (0, 1) 방문
(0, 0) pop
(1, 0), (0, 1) push
큐 : (1, 0), (0, 1)
3. (1, 0) 주위 (2, 0), (1, 1) 방문
(1, 0) pop
(2, 0), (1, 1) push
큐 : (0, 1), (2, 0), (1, 1)
3. (0, 1) 주위 방문 -> 모두 방문하거나 연결되지 않은 부분이니 넘어감
(0, 1) pop
큐 : (2, 0), (1, 1)
4. (2, 0) 주위 방문 -> 모두 방문하거나 연결되지 않은 부분이니 넘어감
(2, 0) pop
큐 : (1, 1)
5. (1, 1) 주위 방문 -> 모두 방문하거나 연결되지 않은 부분이니 넘어감
(1, 1) pop
큐 : empty
큐에 아무것도 남지 않으면, 탐색 완료한다.
BFS 순서
1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복
push 되는 것을 보면 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 N개일 때 O(N)이다.
큐에 좌표를 넣을 때 pair를 이용할 것임.
위의 순서를 코드로 나타내보자
BFS 코드
주어지는 표는 board[][], 방문한 표시를 남기는 표는 vis[][] 이다.
1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
여기서 시작하는 칸은 (0, 0) 이니까 (0, 0)을 넣어준다.
queue<pair<int, int>> Q;
Q.push({0, 0});
vis[0][0] = 1;2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
// 상하좌우를 판단하기 위한 변수 dx, dy
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
pair<int, int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
}3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
// 주어진 board의 크기보다 넘어갈 경우도 아무것도 하지 않는다
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] == 1 || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push({nx, ny});4. 큐가 빌 때까지 2번을 반복
while(!Q.empty()){
// 위에 작성한 코드를 이 안에 넣기
}
5. 최종코드
#include <bits/stdc++.h>
using namespace std;
int board[502][502];
bool vis[502][502];
int n, m; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
queue<pair<int,int> > Q;
vis[0][0] = 1;
Q.push({0,0});
while(!Q.empty()){
pair<int,int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++){
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push({nx,ny});
}
}
}
1. 이어진 그래프의 개수와 크기 찾기
그림의 개수, 가장 큰 그림의 크기 알아내기
1. for문을 돌면서 그림의 시작점이 될 수 있는 위치를 찾고 그 위치에서 BFS 돌리기
2. BFS를 돌면서 push 할 때마다 그림의 크기 +1 하기
3. 큐가 비면 한 그림의 크기가 끝난 것이므로 가장 큰 그림의 크기 업데이터 하기
코드로 고고
1. for문을 돌면서 그림의 시작점이 될 수 있는 위치를 찾고 방문 표시를 남김. 그리고 그 위치에서 BFS 돌리기
BFS 여러 번 돌릴 거라 한번 빼봤다
주의할 건.. 그림이 칠해져 있고 && 방문하지 않았다면 이다.
if(그림이 안 칠해져 있고 || 방문했다면) continue; 해도 된다.
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(board[i][j] == 1 && vis[i][j] != 1) {
cnt++; vis[i][j] = 1;
BFS(i, j);
}
}
}2. BFS를 돌면서 push 할 때마다 그림의 크기 +1 하기
void BFS(int x, int y) {
queue<pair<int, int>> Q;
Q.push({x, y});
int size = 0;
while(!Q.empty()) {
size++;
pair<int, int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push({nx, ny});
}
}
}3. 큐가 비면(BFS가 끝나면) 한 그림의 크기가 끝난 것이므로 가장 큰 그림의 크기 업데이트 하기
ret = max(ret, size);4. 최종코드
#include <iostream>
#include <queue>
using namespace std;
int board[504][504], vis[504][504];
int n, m, cnt;
int ret = 0;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void BFS(int x, int y) {
queue<pair<int, int>> Q;
Q.push({x, y});
int size = 0;
while(!Q.empty()) {
size++;
pair<int, int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push({nx, ny});
}
}
ret = max(ret, size);
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(board[i][j] == 1 && vis[i][j] != 1){
cnt++;
vis[i][j] = 1;
BFS(i, j);
}
}
}
cout << cnt << "\n" << ret;
}
2. 최단경로 거리 계산
갈 수 있는 길로 좌측상단 -> 우측하단으로 가는 최단경로를 구하기
붙어서 입력받는 수 받는 법 : string으로 입력받고 추후에 board[i][j] 형태로 2차원배열로 뜯어볼 수 있다
string board[104];
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> board[i];
}
}1. (0, 0)에서 시작하는 BFS. 큐에 push 할 때마다 vis 값에 +1 해서 넣어주기
칸을 셀 때에는 시작 위치와 도착 위치도 포함하길래 vis[0][0]에 1을 넣고 시작했다.
(바킹독블로그에서는 -1로 초기화하고 마지막에 +1 해줬음)
주의.. board를 string으로 받았기 때문에 길인지 벽인지 판단할 때 '1', '0'처럼 문자를 비교해야 한다.
늘어나는 값은 vis[cur.first][cur.second] + 1
queue<pair<int, int>> Q;
vis[0][0] = 1;
Q.push({0,0});
while(!Q.empty()) {
pair<int, int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(vis[nx][ny] > 0 || board[nx][ny] == '0') continue;
vis[nx][ny] = vis[cur.first][cur.second] + 1;
Q.push({nx, ny});
}
}
2. vis[n-1][n+1] 값을 출력해 준다.
cout << vis[n-1][m-1] << "\n";
3. 최종코드
#include <iostream>
#include <queue>
using namespace std;
string board[104];
int vis[104][104];
int n, m, cnt;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> board[i];
}
queue<pair<int, int>> Q;
vis[0][0] = 1;
Q.push({0,0});
while(!Q.empty()) {
pair<int, int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(vis[nx][ny] > 0 || board[nx][ny] == '0') continue;
vis[nx][ny] = vis[cur.first][cur.second] + 1;
Q.push({nx, ny});
}
}
cout << vis[n-1][m-1] << "\n";
}
3. 시작점이 여러 개
익은 토마토 == 1, 익지 않은 토마토 == 0, 벽 == -1
익은 토마토가 인접하면 익지 않은 토마토가 익는다.
익을 때까지 최소 날짜를 출력한다. 익지 않은 토마토가 있으면 -1을 출력한다.
익은 토마토를 기준으로 하나씩 BFS를 돌리고 -> 퍼지는 날짜를 짚어넣을 때 기존 값보다 작으면 집어넣는다.
이런 식으로 하면 시간초과가 걸린다.
BFS 하나 돌리는데 시간복잡도 O(NM)
토마토의 최대개수 NM개
전체 시간복잡도 O(N^2M^2)
N과 M의 최대가 1000이므로 O(N^2M^2) = O(10^12) 이니까 아마 1초 안에 안될 거다.
시작점이 여러 개일 때는 시작점을 모두 큐에 넣는다.
1. 시작점을 모두 큐에 넣음
2. 최단거리 구하듯 1씩 키우는 BFS 수행
3. 배열을 돌면서 가장 큰 값을 출력, 안 익은 토마토를 만나면 -1을 출력
1. 시작점을 모두 큐에 넣음
주의.. 맨날 이거 때문에 틀리는데 행과열이.. 반대로 입력 들어온다. for문 돌릴 때 헷갈리지 말기
안 익은 토마토는 vis = -1
queue<pair<int, int>> Q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> board[i][j];
if(board[i][j] == 1) {
Q.push({i, j});
}
if(board[i][j] == 0) {
vis[i][j] = -1;
}
}
}
2. 최단거리 구하듯 1씩 키우는 BFS 수행
익은 토마토 + 벽 일 경우 모두 vis[x][y] >= 0이다.
while(!Q.empty()) {
pair<int, int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(vis[nx][ny]>= 0) continue;
vis[nx][ny] = vis[cur.first][cur.second] + 1;
Q.push({nx, ny});
}
}
3. 배열을 돌면서 가장 큰 값을 출력, 안익은 토마토를 만나면 -1을 출력
vis에 최종적으로 있는 수
-1 : 안익은 토마토
0 : 벽 또는 처음 익은 토마토 위치
양수 : 익은 토마토의 영향을 받아 익은 토마토
int mx = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(vis[i][j] == -1) {
cout << "-1\n";
return 0;
}
mx = max(mx, vis[i][j]);
}
}
4. 최종코드
#include <iostream>
#include <queue>
using namespace std;
int board[1004][1004], vis[1004][1004];
int n, m, cnt;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main() {
cin >> m >> n;
queue<pair<int, int>> Q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> board[i][j];
if(board[i][j] == 1) {
Q.push({i, j});
}
if(board[i][j] == 0) {
vis[i][j] = -1;
}
}
}
while(!Q.empty()) {
pair<int, int> cur = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(vis[nx][ny]>= 0) continue;
vis[nx][ny] = vis[cur.first][cur.second] + 1;
Q.push({nx, ny});
}
}
int mx = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(vis[i][j] == -1) {
cout << "-1\n";
return 0;
}
mx = max(mx, vis[i][j]);
}
}
cout << mx << "\n";
}
4. 1차원에서의 BFS
BOJ 1697 숨바꼭질
수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
상하좌우 해주듯 세 가지의 경우를 돌린다.
1. vis 전체를 -1 처리, 수빈이의 시작점은 0
2. 방문할 때마다 +1 처리
3. 동생의 위치 값 출력
1. vis 전체를 -1 처리, 수빈이의 시작점은 0
cin >> n >> m;
fill(vis, vis+100001, -1);
vis[n] = 0;
2. 방문할때마다 +1 처리
int dx[3] = {cur+1, cur-1, cur*2}; // 방문할 위치
queue<int> Q;
Q.push(n);
while(vis[m] == -1) {
int cur = Q.front();
Q.pop();
int dx[3] = {cur+1, cur-1, cur*2};
for(int i = 0; i < 3; i++) {
int nx = dx[i];
if(nx < 0 || nx > 100000) continue;
if(vis[nx] != -1) continue;
vis[nx] = vis[cur] + 1;
Q.push(nx);
}
}
3. 동생의 위치 값 출력
cout << vis[m];
4. 최종코드
#include <iostream>
#include <queue>
using namespace std;
int vis[100002];
int n, m;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
fill(vis, vis+100001, -1);
vis[n] = 0;
queue<int> Q;
Q.push(n);
while(vis[m] == -1) {
int cur = Q.front();
Q.pop();
int dx[3] = {cur+1, cur-1, cur*2};
for(int i = 0; i < 3; i++) {
int nx = dx[i];
if(nx < 0 || nx > 100000) continue;
if(vis[nx] != -1) continue;
vis[nx] = vis[cur] + 1;
Q.push(nx);
}
}
cout << vis[m];
}다른 코드들은 아래의 코드를 제외하고 작성해도 통과하던데 이건 제외하면 메모리초과가 뜬다
ios::sync_with_stdio(0);
cin.tie(0);
'CS > 알고리즘' 카테고리의 다른 글
| 재귀 정리 (c++) (0) | 2023.04.19 |
|---|---|
| DFS 정리 (c++) (0) | 2023.04.18 |
