컴공댕이 공부일지
[실전 알고리즘] 0x09강 | 너비 우선 탐색 (BFS) - 응용 문제 유형별로 풀어보기 📝 본문
🔎 BFS란?
BFS와 DFS를 쉽게 설명하자면,
가까운 이웃부터 좀좀따리 파면서 탐색. 한 단계씩 나아가며 가까운 정점들을 다 방문함 - 큐로 구현
드라마 정주행하듯 끝까지 깊이 탐색. 더이상 못 파면 이전으로 돌아가 다른 경로 탐색. - 스택과 재귀로 구현
BFS: 가까운 것부터 차례대로 탐색 → 큐 사용 → 최단 경로 탐색에 유리
DFS: 깊게 탐색 후 되돌아감 → 스택 또는 재귀 사용 → 경로를 깊이 있게 탐색
이번 글에서는 바킹독 선생님의 강의를 기반으로, BFS의 문제 유형 여러 가지를 풀이해볼 것이다.
📝 BFS 기초 예제
백준 1926번 그림 - 영역 탐색. 2차원 배열에서 가장 넓은 영역 면적 찾기. BFS의 기본 예제 !
https://www.acmicpc.net/problem/1926
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int paper[502][502];
int vis[502][502];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int max = 0, area = 0, cnt = 0;
queue<pair<int,int>> q;
int n, m;
cin >> n >> m;
// 도화지 입력받기
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin >> paper[i][j];
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(!vis[i][j] && paper[i][j]==1) { // 아직 방문도 안하고, 1인 칸부터 새로 시작.
q.push({i, j});
vis[i][j]=1;
cnt ++;
while(!q.empty()){
pair<int, int> cur = q.front();
q.pop(); area++;
for(int i=0; i<4; i++) {
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if(x<0 || x>=n || y<0 || y>=m) continue; // 행렬 범위 넘어갔으면 패스
if(vis[x][y] || paper[x][y]==0) continue; // 이미 방문 or 0이면 패스
vis[x][y]=1;
q.push({x,y});
}
}
if(max<area) max = area; //최대넓이 갱신
area = 0; // 넓이 초기화
}
}
}
cout << cnt << '\n' << max;
return 0;
}
📝 문제 유형 1) 거리 측정
백준 2178번 미로탐색
- 2차원 좌표에서, 이동 최단거리 구하는 문제
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int maze[102][102];
int dist[102][102];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m;
string input;
cin >> n >> m;
cin.ignore(); // 개행 무시
// 미로 입력받기
for(int i=0; i<n; i++) {
getline(cin, input);
for(int j=0; j<m; j++) {
maze[i][j] = input[j]-'0';
}
}
// dist 배열 -1로 초기화
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
dist[i][j] = -1;
}
}
queue<pair<int,int>> q;
q.push({0,0});
dist[0][0] = 1;
// BFS로 최단거리 찾기
while(!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for(int i=0; i<4; i++) {
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if(x<0 || x>=n || y<0 || y>=m) continue; // 범위 벗어나면 패스
if(dist[x][y]!=-1 || maze[x][y]==0) continue; // 해당 칸이 0이거나 이미 채워졌으면 패스..
q.push({x, y});
dist[x][y] = dist[cur.first][cur.second]+1 ; // 현재 칸보다 이동거리 +1
}
}
cout << dist[n-1][m-1];
return 0;
}
시작점을 큐에 넣고 시작해서, 칸마다 거리를 넣어두면 이웃 노드를 모두 탐색하는 BFS의 특성대로, 가능한 모든 경로를 자연스레 탐색하게 된다. 한 칸 씩 나아가며 1씩 더해, 모든 칸의 시작점과의 거리를 계산하므로 최단 거리도 구할 수 있다. 그러나 다음 강의에서 배울 DFS를 활용하면, BFS의 경우처럼 가능한 모든 관계를 살펴보지 않아도 최단거리를 구할 수 있다. 따라서, 최단 경로를 찾는 문제에는 주로 DFS를 쓴다고 한다..? 정확한 사실인지 잘 모르겠음ㅎ DFS 공부해보고 판단해야겟다.
📝 문제 유형 2) 시작점이 여러개인 BFS
백준 7576번 토마토
- 시작점이 여러개인 BFS -> 그냥 모든 시작점을 큐에 넣고 BFS 돌기 ~!
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int tmt[1002][1002];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m, max=0 ;
queue<pair<int,int>> q;
cin >> m >> n;
// 토마토 입력
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin >> tmt[i][j];
if(tmt[i][j] == 1) q.push({i,j});
//익은 토마토는 모두 큐에 넣고 시작 - 시작점이 여러개인 BFS
}
}
// BFS
while(!q.empty()) {
pair<int,int> cur = q.front();
q.pop();
for(int i=0; i<4; i++) {
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if(x<0 || x>=n || y<0 || y>=m) continue; // 범위밖 패스
if(tmt[x][y]!=0) continue; // 안익은 토마토(0) 아니고, 빈칸(-1)이거나 익은 토마토(1)면 패스
tmt[x][y] = tmt[cur.first][cur.second] + 1; // 이전칸에서 +1;
q.push({x, y});
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(tmt[i][j]==0) { // 안익은 토마토 남아있으면 -1 출력
cout << "-1";
return 0;
}
if(max<tmt[i][j]) max=tmt[i][j]; // 익은 토마토와의 최장거리 갱신
}
}
cout << max-1;
return 0;
}
익은 토마토들이 인접 토마토들을 한칸씩 물들이는 BFS. 단, 익은 토마토가 한 개가 아닌 여러 개이므로, 시작점이 여러개인 BFS 유형인 것이다. 근데 걍 시작점들 다 큐에 넣어두고 BFS 돌리면 된다 ~!
백준 7569번 토마토
- 3차원 토마토 문제 ;위의 토마토 문제와 똑같은데 3차원이라, 인접칸이 상하좌우 4개가 아닌 6개임. 튜플을 이용해 구현하면 된다.
#include <iostream>
#include <tuple>
#include <queue>
using namespace std;
typedef tuple<int, int, int> t;
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL);
int tmt[101][101][101];
int n, m, h, max = 0;
// 상하좌우앞뒤
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
queue<t> q;
cin >> m >> n >> h;
for(int i=0; i<h; i++) { // 높이
for(int j=0; j<n; j++) { // 행
for(int k=0; k<m; k++) { // 열
cin >> tmt[j][k][i];
if(tmt[j][k][i]==1) q.push({j,k,i}); //익은 토마토 큐에 넣기.
}
}
}
// BFS
while(!q.empty()) {
t cur = q.front();
q.pop();
for(int i=0; i<6; i++) {
int x = get<0>(cur) + dx[i];
int y = get<1>(cur) + dy[i];
int z = get<2>(cur) + dz[i];
if(x<0 || x>=n || y<0 || y>=m || z<0 || z>=h ) continue; //범위밖 토마토 패스
if(tmt[x][y][z]!=0) continue; // 안익은 토마토만 취급
tmt[x][y][z] = tmt[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
q.push({x,y,z}); // 새롭게 익힌 토마토 큐에 넣기
}
}
for(int i=0; i<h; i++) {
for(int j=0; j<n; j++) {
for(int k=0; k<m; k++) {
if(tmt[j][k][i]==0) { // 안익은 토마토 여전히 존재
cout << "-1";
return 0;
}
if(max<tmt[j][k][i]) max = tmt[j][k][i];
}
}
}
cout << max-1;
return 0;
}풀이 자체는 2차원이랑 똑같은데.. 3중 for문으로 행,열,높이 받아서 쓰는게... 인덱스 i j k 순서가 헷갈려서 좀 어지러웠닿..
📝 문제 유형 3) 시작점이 두 종류인 BFS
백준 4179번 불!
- 시작점이 두 종류 BFS -> 각각을 BFS 돌린 후, 조건에 따라 순차적으로 처리 !
이 문제는 일단, 불이 퍼져나가는 BFS를 돌린 후에, 각 칸별로 언제 먼저 불이 붙는 지 계산해두고, 이후에 지훈이의 이동을 고려한다.
첫 번째 풀이
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int fire[1001][1001]; // 불이 번지는 데 걸리는 시간 저장
int jh[1001][1001]; // 지훈이의 이동 시간 저장
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int r, c;
char tmp;
cin >> r >> c;
queue<pair<int,int>> q_jh;
queue<pair<int,int>> q_fire;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
cin >> tmp;
switch(tmp) {
case '#':
fire[i][j] = -1;
jh[i][j] = -1;
break;
case 'J':
q_jh.push({i, j});
jh[i][j] = 1;
break;
case 'F':
q_fire.push({i, j});
fire[i][j] = 1;
break;
}
}
}
// 불 번져나가는 시간 계산하는 BFS
while(!q_fire.empty()) {
pair<int,int> cur = q_fire.front();
q_fire.pop();
for(int i=0; i<4; i++) {
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if(x<0 || x>=r || y<0 || y>=c) continue; // 범위 외 패스
if(fire[x][y]!=0) continue; // 빈 공간이 아닌 경우 패스 -> 벽이거나 이미 채워졌거나.
fire[x][y] = fire[cur.first][cur.second] + 1;
q_fire.push({x,y});
}
}
// 지훈이 이동하는 BFS
while(!q_jh.empty()) {
pair<int,int> cur = q_jh.front();
q_jh.pop();
for(int i=0; i<4; i++) {
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if(x<0 || x>=r || y<0 || y>=c) continue; // 범위 외 패스
if(jh[x][y]!=0) continue; // 빈 공간이 아닌 경우 패스
jh[x][y] = jh[cur.first][cur.second] + 1;
q_jh.push({x,y});
}
}
int min_t = 10000;
bool flag = false;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(i==0 || i==r-1 || j==0 || j==c-1) { // 가장자리 좌표에 대해
if(jh[i][j]==0) continue; // 지훈이가 닿지 못한 곳은 비교 제외. 1️⃣
if(fire[i][j] > jh[i][j] || fire[i][j]==0) { // 불이 안 난 곳이거나2️⃣, 불 난 시간보다 지훈이의 이동시간이 짧으면
min_t = min(min_t, jh[i][j]);
flag = true;
}
}
}
}
if (flag) {
cout << min_t;
} else {
cout << "IMPOSSIBLE";
}
return 0;
}
둘의 BFS를 각각 돌린 후에, 가장자리 좌표에 담긴 값을 비교해서 불보다 지훈이가 빨랐다면 탈출 가능한 것으로 판단해 최소 시간과 비교하는 식으로 문제를 풀면 된다.
즉 jh 배열의 값과 fire 배열의 값을 비교해 jh이 작으면, 지훈이가 불보다 빠른 것이니 min_t과 비교하는 과정을 거친다. 문제는 jh 배열과 fire배열 모두 초기화가 0으로 되어있다는 것이다. 단순 jh < fire 인 좌표를 찾으면 오류가 발생한다. 그래서 아래와 같은 두 가지 코너케이스를 추가했다. (위 코드 상에 1️⃣2️⃣로 표시된 부분)
1️⃣ 지훈이가 이동하지 못한 칸이라 jh 배열값이 0인 경우 → jh < fire 여도 탈출 불가능한 칸으로 간주
지훈이의 이동은 1부터 시작되도록 했는데, 배열 빈칸이 0으로 초기화되어있어 벽에 막혀 지훈이가 미쳐 닿지 못한 곳은 배열값이 0으로 남아있다는 것이다. 이러면, 무조건 그 장소가 불보다 빨리 탈출한 것으로 판단되는 오류가 있었다. 그래서 지훈이가 닿지 못한 곳 즉 jh 배열값이 0인 부분은 제외하는 조건문을 하나 걸었다.
2️⃣ 불이 퍼지지 않은 칸이라 fire 배열값이 0인 경우 → jh > fire 여도 탈출 가능한 칸으로 간주
그리고 마찬가지로 fire배열도 1부터 퍼지지만, 미처 불이 닿지 않은 곳은 0으로 초기화되어있다. 불이 닿지 않은 곳은 항상 지훈이가 탈출할 수 있는 공간으로 간주되어야하는데, 0으로 초기화되어있어 jh 값보다 늘 작아 제외되고 있었다. 그러나, 앞서 말했듯 불이 전혀 닿지 않는 곳이니 탈출 가능하다고 판단해야한다. 따라서 fire 값이 0인 경우도 탈출 가능한 칸으로 취급해, 최소 시간과 비교하는 구문으로 들어가도록 설정했다.
배열의 초기화가 0으로 되어 jh < fire 를 비교하는 과정에서 위 두가지의 예외 사례가 발생하니 주의해야한다.
그리고 바킹독 님의 코드를 보고, 더 효율적인 코드로 바꿔보았다. (실행시간 60->36ms)
내가 위 코드에서 간과한 것이 있는데, min_t을 따로 구할 필요 없이, 범위를 벗어나 가장자리에 도달했다는 것은 탈출에 성공했다는 뜻이므로 처음 범위를 벗어난 순간의 지훈이의 이동거리를 출력하고 즉시 리턴하면 된다. 다만 이렇게 즉시 return 하려면, 지훈이가 움직일 수 없는 칸은 아예 계산하면 안된다.
나는 아예 지훈이 따로 불 따로 BFS를 진행한 후에 마지막에 가장자리들을 비교하는 방식으로 풀었는데, 바킹독님처럼 지훈이가 불보다 빨리 갈 수 있을 때만 이동을 계산하게 되면, 가장자리에 간 순간 return하고 최소 탈출 시간을 구할 수 있다.
두 번째 풀이
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int fire[1001][1001]; // 불이 번지는 데 걸리는 시간 저장
int jh[1001][1001]; // 지훈이의 이동 시간 저장
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int r, c;
char tmp;
cin >> r >> c;
queue<pair<int,int>> q_jh;
queue<pair<int,int>> q_fire;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
cin >> tmp;
switch(tmp) {
case '#':
fire[i][j] = -1;
jh[i][j] = -1;
break;
case 'J':
q_jh.push({i, j});
jh[i][j] = 1;
break;
case 'F':
q_fire.push({i, j});
fire[i][j] = 1;
break;
}
}
}
// 불 번져나가는 시간 계산하는 BFS
while(!q_fire.empty()) {
pair<int,int> cur = q_fire.front();
q_fire.pop();
for(int i=0; i<4; i++) {
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if(x<0 || x>=r || y<0 || y>=c) continue; // 범위 외 패스
if(fire[x][y]!=0) continue; // 빈 공간이 아닌 경우 패스 -> 벽이거나 이미 채워졌거나.
fire[x][y] = fire[cur.first][cur.second] + 1;
q_fire.push({x,y});
}
}
// 지훈이 이동하는 BFS
while(!q_jh.empty()) {
pair<int,int> cur = q_jh.front();
q_jh.pop();
for(int i=0; i<4; i++) {
int x = cur.first + dx[i];
int y = cur.second + dy[i];
// 최초로 가장자리에 도달한 순간 -> 탈출 가능한 최소 시간임 !
if(x<0 || x>=r || y<0 || y>=c) {
cout << jh[cur.first][cur.second];
return 0;
}
if(jh[x][y]!=0) continue; // 빈 공간이 아닌 경우 패스
// 지훈이는 불보다 빨리 이동 가능할 때만 이동 !
if (fire[x][y] == 0 || jh[cur.first][cur.second] + 1 < fire[x][y]) {
jh[x][y] = jh[cur.first][cur.second] + 1;
q_jh.push({x,y});
}
}
}
cout << "IMPOSSIBLE";
return 0;
}
지훈이의 이동거리를 무작정 다 계산하지 않고, 불보다 빨리 갈 수 있을 때만 이동하고, 가장자리로 탈출하는 순간 return 하도록 하니 실행시간이 엄청 줄었다 !
+ 추가로, 이 문제는 지훈이는 불의 이동에 영향을 받지만, 불은 지훈이의 이동에 영향을 주지 않는다. 따라서 불을 먼저 BFS하고나서, 지훈이의 BFS를 진행해도 문제가 없다. 그런데 두 종류의 시작점이 만약 서로 영향을 준다면? 이렇게 순차적으로 BFS를 돌리는 것으로는 문제가 해결되지 않는다. 그 경우에은 두 시작점을 동시에 진행시켜야 한다. 이렇게 두 시작점이 서로 영향을 주는 문제 유형(백준 18809번 문제)은 백트래킹 기법을 추가로 알고 있어야 해결이 가능하다고 함.
📝 문제 유형 4) 1차원에서의 BFS
백준 1697번 숨바꼭질
- 1차원 BFS는 이전에 상하좌우로 퍼져나가는 문제 유형과는 조금 다르지만, 마찬가지로 BFS로 풀이하면 된다 !
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
queue<int> q;
int dist[100002];
cin >> n >> k;
q.push(n);
fill(dist, dist+100001, -1); // -1로 배열 초기화
dist[n] = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(int nxt : {cur-1, cur+1, cur*2}) {
if(nxt<0 || nxt>100000) continue; // 범위 외 패스
if(dist[nxt] != -1) continue; // 이미 채워진 값이면 패스
dist[nxt] = dist[cur] + 1;
q.push(nxt);
}
}
cout << dist[k];
return 0;
}
여기서 주의할 점은, BFS를 돌 때 범위 외라서 패스하는 부분의 범위가 10만인 이유를 고민해봐야한다. n과 k의 범위가 10만 이하인거지, +1, -1, *2로 이동하다보면 10만의 범위를 벗어날 수도 있다. 그럼 최대 20만까지도 계산이 될 수 있다.
그런데 20만에서 10만까지 돌아오려면 결국 -1 연산을 해줘야하고.. 그럼 -1연산을 약 10만번 이상 해야 k로 다시 돌아올 수 있다. 그러므로 k값의 최대치인 10만에 가까워졌을 땐, *2연산보다 +-연산을 사용하는 것이 더 효율적인 것이다. 따라서, 20만까지는 BFS 범위에 고려하지 않아도 된다. 따라서 범위는 10만이 된 것이다. 무작정 k와 n의 범위와 같다고 생각해버리면 오류를 범할 수도 있으니 조심하라는 스승님의 말씀 ! :)
나같은 감자는 미처 생각못한 부분도 이렇게 논리있게 짚어주심 ... 진짜 강의도 잘 하시지만 내가 짠 코드랑 비교해볼때마다 아 이렇게 깔끔하게 효율적으로 쓸 수도 있구나 싶어 정말 많이 배우고 있다. 코테 공부 겸 코드리뷰도 되고있음ㅇㅇ
휴학하고 구멍 뻥뻥난 나에 잔디밭 ..🌿 언제까지고 이러케 데굴거릴 순 업서~ 그래서 다시 백준도 매일 풀고 티스토리도 굴려봅니다ㅏㅏ 이 글 쓰는데 거의 사흘은 걸린 듯 ... 요새 집중력 3초 이슈로 오래 앉아있질 못하는데.. 그래도 매일매일 꾸준히 한 문제씩은 풀어보려 노력 중. 꾸준하기 참 .. 어렵다 .. 🔥
암튼 오래도 걸린... BFS 정리글 드디어 마칩니다 !! 바킹독 선생님 보고계신가여 너무 감사해여 ,,,, 완강까지 꾸준히 달려보겠나이다 ... 아쟈아쟈
[실전 알고리즘] 0x09강 - BFS
안녕하세요 여러분, 드디어 올 것이 왔습니다. 마음의 준비를 단단히 하셔야 합니다.. 드디어 실전 알고리즘 강의에서 첫 번째 고비에 도달했는데 이 강의와 함께 이번 고비를 잘 헤쳐나가면 좋
blog.encrypted.gg
'CS > 알고리즘' 카테고리의 다른 글
| [실전 알고리즘] 0x0A강 | 깊이 우선 탐색 (DFS) - 스택으로 DFS 구현하기 / DFS와 BFS의 차이? (0) | 2025.02.13 |
|---|---|
| [실전 알고리즘] 0x01강 - 🔎 정수 및 실수 자료형의 특징 / 2의 보수법 (0) | 2025.01.15 |
| [ 동적계획법 ] top-down, bottom up (상담시간 퇴사 문제) (0) | 2024.04.02 |
| [ 동적프로그래밍 ] 개념 (피보나치, 외발뛰기) (0) | 2024.04.02 |
| [ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이 (1) | 2024.03.28 |
