C++:: BFS & STL:: pair

참고 내용

https://blog.encrypted.gg/941

정의

그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

BFS(Breadth-First Search) : 너비 우선 탐색

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

BFS 과정

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

모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)

주의할 점

1. 시작점에 방문했다는 표시를 남기지 않는다.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.

문제 유형

1. Flood Fill : 백준 1926 그림

2. 거리 측정 : 백준 2178 미로 탐색

    방문했는지 > 배열에 거리를 저장하기

3. 시작점이 여러 개일 때 : 백준 7576 토마토

    여러 개의 시작점을 큐에 먼저 넣고 while문 돌리기

4-1. 시작점이 두 종류일 때(A가 B한테만 영향을 미치는 경우) : 백준 4179 불!

    BFS를 각각에 대해 돌리면 됨

4-2. 시작점이 두 종류일 때(A와 B가 서로 영향을 주고 받을 때): 백준 18809 Gaaaaaaaaaarden

    BFS를 시간 순으로 A, B 동시에 돌려야 함

5. 1차원에서의 BFS : 백준 1697 숨바꼭질

STL:: pair

자료형 선언 : pair<자료형, 자료형>
pair 생성 : make_pair(__, __) / C++11에서는 {__, __}
자료형 접근 : pair.first, pair.second
비교: first 먼저 비교 후 second 비교

예제 코드

#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
}

BFS 기본 틀

#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];
      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});
    }
  }
}