[알고리즘 공부] 실전 알고리즘 9강-BFS

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

알고리즘 설명

BFS (Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

BFS 알고리즘에서는 좌표를 담을 queue가 필요하다.

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌때까지 2번을 반복
5. 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일때 O(N)

pair는 두 원소를 묶어서 다닐 수 있는 STL로 이 pair는 미리 대소 관계가 설정되어 있다.
알아서 앞쪽의 값을 먼저 비교하고, 이후 뒤쪽의 값을 비교한다.
BFS를 구현할 때 queue에 좌표를 넣어야하는데 이때 pair를 사용한다.

---

구현

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // 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);
  queue<pair<int,int> > Q;
  vis[0][0] = 1; // (0, 0)을 방문했다고 명시
  Q.push({0,0}); // 큐에 시작점인 (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]; // x가 행, y가 열로 생각하는게 좋다.
      int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감, 이게 반드시 먼저 확인되어야 함 
      if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
      vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
      Q.push({nx,ny});
    }
  }
}

구현할 때 자주하는 실수

1. 시작점을 방문은 했는데 방문했다는 표시를 남기지 않는다.
2. queue에 넣을 때 방문했다는 표시를 남기지 않고 queue에서 빼낼때 방문했다는 표시를 남기는 경우에는 같은 칸이 queue에 여러번 들어갈 수 있어서 시간초과나 메모리 초과가 발생할 수 있다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크가 잘못된 경우가 있다. 코드에서 nx, ny가 범위 밖을 벗어난 경우를 빼먹었거나 이상하게 구현한 상태를 말한다.

---

백준 1926번

1. 상하좌우에 연결된 그림의 크기를 알아내기 -> pop 갯수로 파악
2. 도화지에 있는 모든 그림을 찾아내기 -> 이중 반복문을 통해 BFS의 시작점이 될 수 있는지를 체크

백준 2178번

1. 좌측 상단에서 우측 하단으로 가는 최단 경로의 길이는 찾는 문제이다.
2. 빨간색 칸은 현재 보고 있는 칸이고 검정색 칸은 추가되는 칸이다. 현재 보고 있는 칸으로부터 추가되는 인접한 검정색 칸은 현재 보고 있는 칸이랑 1만큼 떨어져 있다. 이 성질을 이용해서 시작점과의 거리를 전부 계산할 수 있다.
   
3. 거리를 저장할 dist 배열을 두고 상하좌우의 칸을 볼 때 값을 잘 넣어주면 된다. 이 배열을 미리 -1로 초기화해두면 굳이 vis 배열을 따로 두지 않아도 방문 여부를 확인할 수 있다.

백준 7576번

1. 시작점이 여러개인 BFS를 도는 문제이다. 모든 시작점을 queue에 넣고 BFS를 돌면 된다.
2. BFS를 돌 때 queue에 쌓이는 순서는 반드시 거리순이다.
   

백준 4179번

1. 지훈이에 대한 BFS와 불에 대한 BFS를 모두 돌리면 되는 문제이다.
2. 시작점이 두 종류인 문제는 지훈이는 불의 영향을 받지만 불은 지훈이의 영향을 받지 않아서 불만 먼저 쭉 전파를 시키는게 가능했다. 그런데 A와 B 두 시작점이 존재하고 서로가 서로에게 영향을 준다면 어느 하나를 끝까지 먼저 전파시키는건 불가능하다. 따라서 서로가 독립적이지 않고 영향을 준다면 하나 먼저 처리하고 나머지를 처리하는 방법은 불가능한 것이다.