[알고리즘/C++] BFS

- 출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

'강좌/실전 알고리즘' 카테고리의 글 목록

- BFS(Breadth First Search)
  - 배열 방문 시 너비를 우선으로 방문
  - 그래프 순회 시 사용하는 알고리즘(DFS, BFS) 중 하나

- BFS의 구현(2차원 배열)
  1. 0,0좌표를 큐에 입력
  2. 큐의 맨 앞 데이터를 deque
  3. 해당 좌표의 접근 가능한 상/하/좌/우를 enque,
    - 조건을 만족하는 경우 해당 좌표에는 방문 표시
    - 이미 방문한 코드는 동작 생략
  4. 2~3을 반복
  5. 큐가 빌 경우 BFS 동작이 완료

- STL pair
  - <utility> 헤더에 존재
  - pair<자료형1, 자료형2>로 구현
  - 두개의 자료 구조를 동시에 사용할 때 사용
  - make_pair 혹은 중괄호(C++11이상)로 값 대입
  - pair간 비교시 앞의 데이터부터 순서대로 비교
    - ex. <1, 2>, <1, 3> : 앞의 1은 같고, 뒤의 2, 3 비교시 뒤가 더 크므로 뒤 자료가 더 크다고 확인
  - pair data는 pair.fist, pair.second로 앞/뒤의 데이터를 접근 가능

- 배열을 이용한 큐의 구현

#include<iostream>
#include<queue>
#include<utility>

int arr[100][100];
bool visit[100][100];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {1, 0, -1, 0};

int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<pair<int, int>> q;
    
    visit[0][0] = 1;
    q.push(make_pair(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 > 100 || ny < 0 || ny > 100) continue;
        if(visit[nx][ny] || arr[nx][ny] != 1) continue
        //상하좌우 좌표가 배열을 벗어나거나, 방문했거나, 조건을 불만족할 시 통과
        
        visit[nx][ny] = 1; // 방문 표시
        q.push(make_pair(nx, ny)); //새 좌표를 enque
      }
    }
}