[바킹독의 실전 알고리즘] 0x09강 - BFS

BFS(Breadth First Search)

• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
• -> 너비 우선으로 방문?? 
• 그래프에서 모든 노드를 방문하는 알고리즘
  그래프: 정점과 간선으로 이뤄진 자료구조

예시

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소 꺼내 그 칸에 상하좌우로 인접한 칸에 대해 3번 진행
3. 해당 칸 이전에 방문했다면 아무것도 하지 않고, 처음 방문했다면 방문했다는 표시 남기고 해당 칸을 큐에 삽입
4. 큐 빌 때까지 2번 반복

=> 모든 칸이 큐에 1번씩 들어감

-> 시간복잡도는 칸이 N개일 때 O(N)

ex. 행이 R개, 열이 C개 -> O(RC)

(0, 0)과 상하좌우로 이어진 모든 파란칸 확인
좌표를 담을 큐 필요
(0, 0)에 방문했다는 표시 + 해당 칸 -> 큐에 넣음

큐가 빌 때까지 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업 반복

step 1
큐의 front: (0, 0) -> pop 
(0, 0)과 상하좌우로 인접한 (0, 1)과 (1, 0) 모두 파란 칸 -> 아직 방문 X
=> 2개의 칸에 방문했다는 표시 + 큐에 넣음

step 2
큐의 front: (0, 1) -> pop
(0, 1)과 상하좌우로 인접한 (0, 2) -> 아직 방문 X
=> (0, 2)에 방문했다는 표시 + 큐에 넣음

=> 큐의 front -> pop + 인접한 칸 중에 방문 X 파란색 칸에 표시 + 큐에 넣음

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	pair<int, int> t1 = make_pair(10, 13);
    pair<int, int> t2  = {4, 6}; // C++11
    cout << t2.first << ' ' << t2.second << '\n'; // 4 6
    if(t2 < t1) cout << "t2 < t1"; // t2 < t1
}

값의 접근 -> first, second 부름
pair에는 미리 대소 관계 설정되어 있음
=> 알아서 앞쪽의 값 먼저 비교, 이후 뒤쪽의 값 비교

BFS 구현 시 큐에 좌표 넣어야 함 -> pair 사용

#include <bits/stdc++.h>
using namespace std;

// pair에서 first, second -> t.X, t.Y
#define X first
#define Y second 

// 1: 파란 칸, 0: 빨간 칸
int board[502][502] =
{...}; 

bool vis[502][502]; 
int n = 7, m = 10; 
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 아래, R, L, 위

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  queue<pair<int,int> > Q;
  vis[0][0] = 1; 
  Q.push({0,0});
  
  while(!Q.empty()){
    pair<int,int> cur = Q.front(); Q.pop();
    cout << '(' << cur.X << ", " << cur.Y << ") -> ";
    
    for(int dir = 0; dir < 4; dir++){ 
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir]; 
      
      // 범위에 들어오는지 확인
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 
      // 이미 방문한 칸 or 파란 칸 X 경우
      if(vis[nx][ny] || board[nx][ny] != 1) continue; 
      vis[nx][ny] = 1; // (nx, ny) 방문
      Q.push({nx,ny});
    }
  }
}

vis: 방문 여부 저장 변수
=> 예시에서 동그라미 -> vis값을 1로 변경
n = 행의 개수, m = 열의 개수

(0, 0)에 방문 표시 -> vis[0][0] = 1; 
큐에 시작점 (0, 0) 추가 -> Q.push({0,0});

큐의 front에 cur 저장, pop

상하좌우 좌표값 담기
 x: 행 / y: 열
            x-1, y
x, y-1     x, y     x, y+1
            x+1, y
-> int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; 
/ int nx = cur.X + dx[dir]; int ny = cur.Y + dy[dir]

실수

• 시작점에 방문했다는 표시 남기지 X
  • -> 시작점 2번 방문할 수 있음
• 큐에 넣을 때 방문했다는 표시 하는 대신 큐에서 빼낼 때 방문했다는 표시
  • -> 같은 칸이 큐에 여러 번 들어가게 됨 
  • => 시간 초과 or 메모리 초과 발생
• 이웃한 원소가 범위를 벗어났는지에 대한 체크 잘못함
  = nx, ny가 배열 바깥으로 벗어났는지

---

예시

BOJ 1926번: 그림

문제
어떤 큰 도화지에 그림이 그려져 있음
그 그림의 개수, 그 그림 중 넓이가 가장 넓은 것의 넓이 출력
단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의
가로나 세로로 연결된 것은 연결이 된 것, 대각선으로 연결된 것은 떨어진 그림
그림의 넓이 = 그림에 포함된 1의 개수

입력
첫째 줄: 도화지의 세로 크기 n(1 <= n <= 500) / 가로 크기 m(1 <= m <= 500)
두 번째 줄 ~ n+1 줄: 그림의 정보(0과 1이 공백으로 두고 주어짐)
0: 색칠이 안된 부분 / 1: 색칠이 된 부분

 

1. 상하좌우로 연결된 그림의 크기 알아내기
   -> 큐에서 pop 몇 번 하는지 세기
2. 도화지에 있는 모든 그림 찾아내기
   -> 이중 for문으로 각 칸이 BFS의 시작점이 될 수 있는지 체크
   => 시간복잡도: 각 칸의 갯수만큼 O(nm)

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second 

int board[502][502]; 
bool vis[502][502]; 
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; 

int main(){
  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];
  int mx = 0; 
  int num = 0;
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){ 
      if(board[i][j] == 0 || vis[i][j]) continue; 
      num++; 
      queue<pair<int,int> > Q;
      vis[i][j] = 1; 
      Q.push({i,j});
      int area = 0; 
      
      while(!Q.empty()){
        area++; 
        pair<int,int> cur = Q.front(); Q.pop();
        for(int dir = 0; dir < 4; dir++){ 
          int nx = cur.X + dx[dir];
          int ny = cur.Y + 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});
        }
      }
      mx = max(mx, area);
    }
  }
  cout << num << '\n' << mx;
}

이중 for문 -> (i, j)가 BFS의 시작점이 될 수 있는지 확인
빨간칸 or 이미 방문 -> 제외, 이후 그 점을 시작점으로 BFS

while문 안에서 pop이 이뤄질 때마다 area 값 1 증가
-> area 값 = 그림의 넓이

---

응용 1 - 거리 측정

BOJ 2178: 미로 탐색

문제
NxM크기의 배열로 표현되는 미로
1: 이동할 수 있는 칸 / 0: 이동할 수 없는 칸
(1, 1)에서 출발 -> (N, M)의 위치로 이동할 때 지나야 하는 최수의 칸 수
한 칸에서 다른 칸 이동 -> 서로 인접한 칸으로만 이동
칸을 셀 때 시작 위치, 도착 위치 포함

입력
첫째 줄: 두 정수 N, M(2 <= N, M <= 100)
다음 N개 줄: M개의 정수로 미로주어짐

 

미로의 좌측 상단 -> 우측 하단으로 가는 최단 경로의 길이 찾는 문제

BFS 이용 -> 시작점에서 연결된 다른 모든 점으로의 최단 경로 찾음

 

=> 현재 보고 있는 칸으로부터 추가되는 인접한 칸: 거리가 현재 보는 칸보다 1만큼 더 떨어져 있음

• 첫 번째: 빨간색 칸에서 거리: 0, 검정색 칸에서 거리: 1
• 마지막: 빨간색 칸에서 거리: 4, 검정색 칸에서 거리: 5

-> 상하좌우로 연결된 칸들을 방문하는 것 + 시작점과의 거리 계산

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

string board[102];
int dist[102][102]; 
int 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++)
    cin >> board[i];
  for(int i = 0; i < n; i++) fill(dist[i],dist[i]+m,-1);
  queue<pair<int,int> > Q;
  Q.push({0,0});
  dist[0][0] = 0;
  
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue;
      dist[nx][ny] = dist[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
  cout << dist[n-1][m-1]+1;
}

dist 배열: 거리 저장, 상하좌우 칸 볼 때 값 잘 넣기
-> 미리 -1로 초기화 => vis 배열 없어도 방문 여부 확인 O
-> fill ~> 초기화 (이중 for문 사용 가능)
=> vis 대신 dist 사용

---

응용 2 - 시작점이 여러 개일 때

BOJ 7576번: 토마토

문제
창고에 보관하는 토마토 - 잘 익은 것 / 아직 익지 않은 것
보관 후 하루가 지나면, 익은 토마토 영향 -> 인접한 곳에 있는 익지 않은 토마토 익음
하나의 토마토의 인접한 곳: L, R, 앞, 뒤 (4 방향)
대각선 방향에 있는 토마토에 영향 X, 저절로 익는 경우 X
=> 창고에 보관된 토마토 며칠 지나면 다 익는지 최수 일수?

토마토 창고에 보관하는 격자모양 상자들의 크기, 익은 토마토 / 익지 않은 토마토 정보
-> 며칠 지나면 모두 익는지 최소 일수
상자 일부 칸에 토마토 들어있지 않을 수 있음

입력
첫째 줄: 상자의 크기 두 정수 M, N
M: 상자의 가로 칸의 수 / N: 상자의 세로 칸의 수 (2 <= M, N <= 1,000)
둘째 줄 ~ N개의 줄: 하나의 상자에 저장된 토마토들의 정보 = 상자에 담긴 토마토 정보
하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어짐
정수 1: 익은 토마토 / 0: 익지 않은 토마토 / -1: 토마토가 들어있지 않은 칸

• 익은 토마토 1개
  • 익은 토마토가 있는 곳 = 시작점 => BFS
• 익은 토마토 여러 개
  • 해당 위치를 시작점으로 하는 BFS 한 번씩
    -> BFS의 시간복잡도: O(NM), 익은 토마토 최대 NM개 => 총 O(N^2M^)
  • 해결: 모든 시작점을 큐에 넣고 BFS

 

파란색: 익지 않은 토마토 / 초록색: 익은 토마토 / 빨간색: 빈 칸

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int board[1002][1002];
int dist[1002][1002];
int 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 >> 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)
        dist[i][j] = -1;
    }
  }
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist[nx][ny] >= 0) continue;
      dist[nx][ny] = dist[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
  int ans = 0;
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(dist[i][j] == -1){
        cout << -1;
        return 0;
      }
      ans = max(ans, dist[i][j]);
    }
  }
  cout << ans;
}

익은 토마토 -> 큐에 넣음 / 익지 않은 토마토 -> dist 값 -1
전역 변수 int or int 배열 초기화 X -> 0으로 채워짐
=> 익은 토마토 들어있음 or 빈 칸 -> dist 값 0

거리가 가장 먼 것 찾음 
+ 익지 않은 토마토 있는지 확인

 

여러 개의 시작점에서 모든 지점으로의 거리 구하는 문제

 

익은 토마토(거리 0) -> 큐에 넣음

-> 첫 번째 칸 ~> 추가되는 칸: 거리 1

-> 거리 1인 칸들 pop하는 동안 2인 칸들 추가

-> 거리 1인 칸들 다 빠지고 2인 칸들 pop하는 동안 3인 칸들 추가

=> BFS 돌 때 큐에 쌓이는 순서: 거리 순

---

응용 3 - 시작점이 두 종류일 때

BOJ 4179번: 불!

문제
지훈이는 미로에서 일하는데 탈출하도록 도움
미로에서의 지훈이의 위치, 불이 붙은 위치 감안
-> 지훈이가 불에 타기 전 탈출할 수 있는지 여부, 얼마나 빨리 탈출할 수 있는지 결정
지훈이와 불은 매 분마다 한 칸씩 수평 or 수직(비스듬하게 이동 X) 이동
불: 각 지점에서 네 방향으로 확산
지훈: 미로의 가장자리에 접한 공간에서 탈출
지훈이와 불 -> 벽이 있는 공간 통과 X

입력
첫째 줄: 공백으로 구분된 두 정수 R, C (1 <= R, C <= 1000)
R: 미로 행의 개수 / C: 열의 개수
R 줄동안 각각의 미로 행 주어짐
#: 벽 / .: 지나갈 수 있는 공간 / J: 지훈이의 미로에서의 초기 위치(지나갈 수 있는 공간) / F: 불이 난 공간

1. 불에 대한 BFS
   • 각 칸에 불이 전파되는 시간
2. 지훈이에 대한 BFS
   • 지훈이 이동 
   • 지훈이가 특정 칸을 x시간에 최초로 방문 -> 그 칸에 x시간 or 그 이전에 불 붙음 => 그 칸에 못감
     
     • ex. **로 마킹한 칸: 지훈이 2시간이 될 때 방문
       But, 불은 이미 1시간만에 전파 => 지훈이 갈 수 X

BFS 구현에서 큐 안에는 (nx, ny) 살펴볼 때 방문했는지 여부

-> vis[nx][ny] == true or dis[nx][ny] >= 0 확인, 이미 방문한 칸 -> continue

 

+ 해당 칸에 불이 붙은 시간 확인 -> 필요에 따라 continue

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

string board[1002];
int dist1[1002][1002]; 
int dist2[1002][1002]; 
int 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++){
    fill(dist1[i], dist1[i]+m, -1);
    fill(dist2[i], dist2[i]+m, -1);    
  }
  for(int i = 0; i < n; i++)
    cin >> board[i];  
  queue<pair<int,int> > Q1;
  queue<pair<int,int> > Q2;
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(board[i][j] == 'F'){
        Q1.push({i,j});
        dist1[i][j] = 0;        
      }
      if(board[i][j] == 'J'){
        Q2.push({i,j});
        dist2[i][j] = 0;
      }
    }
  }

  while(!Q1.empty()){
    auto cur = Q1.front(); Q1.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue; 
      dist1[nx][ny] = dist1[cur.X][cur.Y]+1;
      Q1.push({nx,ny});
    }
  }

  while(!Q2.empty()){
    auto cur = Q2.front(); Q2.pop();
    
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m){ 
        cout << dist2[cur.X][cur.Y]+1; 
        return 0;
      }
      if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
      if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; 
      dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
      Q2.push({nx,ny});
    }
  }
  cout << "IMPOSSIBLE"; 
}

불에 대한 BFS -> Q1, dist1
지훈이에 대한 BFS -> Q2, dist2

불에 대한 BFS 끝나면 dist1에는 해당 지점에 불이 언제 붙는지 저장
지훈이에 대한 BFS -> 외곽으로 빠져나올 수 있게 함

기존 BFS
: 목적지 정해져 있음 or 더 이상 갈 곳이 없을 때까지 계속 돌리는 상황
현재 문제
: 외곽으로 탈출 = (nx, ny)가 범위 벗어남 
큐에 원소들 거리 순으로 들어감 -> 최초로 탈출한 시간 출력하고 종료

자신이 도착한 시간과 동시에 불이 도착 or 자신보다 불이 더 빨리 도착하는 자리 X

프로그램 종료 X while문 끝남 -> 지훈이 탈출 실패

=> 지훈이의 이동은 불의 전파에 영향 받음 
But, 불의 전파는 지훈이의 이동에 영향 받지 X
-> 불만 먼저 전파 시키는 것이 가능

IF 시작점 A, B 2개, A(불) <-> B(물) 전파 서로 영향
=> 어느 하나 먼저 끝까지 전파 시키기 가능 X
-> 백트래킹 기법 추가
= 두 종류의 BFS에서 BFS 돌 때 어느 하나 독립적 X 서로에게 영향
-> 시간 순으로 A, B 동시에 진행

---

응용 4 - 1차원에서의 BFS

BOJ 1697번: 숨바꼭질

문제
수빈이는 동생과 숨바꼭질
수빈: 현재 점 N(0 <= N <= 100,000) / 동생: 점 K(0 <= K <= 100,000)
수빈이 위치 X일 때, 수빈이 걷거나 순간이동 O
걸음: 1초 후에 X-1 or X+1로 이동
순간이동: 1초 후에 2*X로 이동
수빈이와 동생의 위치 주어졌을 때, 수빈이가 동생 찾을 수 있는 가장 빠른 시간 몇 초 후?

입력
첫 번째 줄: 수빈이가 있는 위치 N, 동생이 있는 위치 K (N, K는 정수)

 

2차원 BFS: 현재 선택된 칸에서 상하좌우로 뻗어나가는 방식

 

BFS 범위 어디까지?

범위 0 ~ 100,000 But, 이동 중에 반드시 0 ~ 100,000 사이 X = 100,000 밖으로 나갔다가 다시 안으로 옴

-> 음수 X -> 가장 빠른 경로 X / 100,000 바깥으로 나갈 수 X -> 나가면 그 이후는 -1

=> 0 ~ 200,000 사이 -> 100,000 나가는 것 자체가 손해

= +1로 100,000 탈출: 손해, *2로 100,000 가능하지만, 그 후 -1 여러 번 하는 것보다 -1 먼저하고 *2 하는 것이 남

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int dist[100002];
int n,k;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  fill(dist, dist+100001,-1);
  dist[n] = 0;
  queue<int> Q;
  Q.push(n);
  
  while(dist[k] == -1){
    int cur = Q.front(); Q.pop();
    
    for(int nxt : {cur-1, cur+1, 2*cur}){
      if(nxt < 0 || nxt > 100000) continue;
      if(dist[nxt] != -1) continue;
      dist[nxt] = dist[cur]+1;
      Q.push(nxt);
    }        
  }
  cout << dist[k];
}

---