c++/ 자료구조&알고리즘 개념 복습하기 - 8 / BFS, pair

한창희·2022년 2월 13일

c++ 정리

c++ 자료구조/알고리즘 개념 복습

목록 보기

8/23

< 그래프 탐색 >

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

< BFS >

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
보통 다차원 배열에서 각 칸을 방문할 시 인접한 상하좌우를 우선으로 탐색
시작하는 칸을 큐에 넣고 방문 표시를 남긴다
큐에서 원소를 꺼내어 해당 칸에 상하좌우 인접한 칸을 체크

< STL pair >

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

pair은 대소 관계 비교 시 first의 값으로 비교 후 second 값을 자동적으로 비교한다
{x,y} 형태로 생성하는 것이 make_pair 보다 조금 더 빠른 것 같다(백준의 동일 문제에서 make_pair 부분만 {x,y} 형태로 변경하니 약간 더 빨라졌다)

< 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 dy[4] = {-1,1,0,0}; 
int dx[4] = {0,0,-1,1};  // 상하좌우 y=행, x=열


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}); // { } 형태로 pair 인자 전달 가능!
    }
  }
}