211229 TIL

BFS 7문제

• 목록

  문제	문제 제목
  1926	그림
  2178	미로 탐색
  7576	토마토
  4179	불!
  1697	숨바꼭질
  1012	유기농 배추
  10026	적록색약

• 새로 배운 내용

  • PS에 사용하는 BFS 코드 기본 형식

    // 0, 0 좌표부터 1을 가진 좌표를 모두 방문하는 BFS
    
    #include <bits/stdc++.h>
    using namespace std;
    #define X first
    #define Y second
    
    int n, m;
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    int board[501][501];
    bool vis[501][501];
    queue<pair<int, int> > q;
    
    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]; // i열 j행에 각 입력 값 받기
    		}
    	}
    	q.push({0, 0}) // 큐에 출발 좌표를 넣어주고
    	vis[0][0] = 1; // = true / vis을 통해 0, 0 좌표에 방문했다는 표시를 남김
    	while (!q.empty()) {
    		pair<int, int> cur = q.front(); q.pop(); // 큐 앞 값을 cur에 저장 후 제거
    		for (int i = 0; i < 4; i++) { // dx, dy 배열을 이용하여 상하좌우 좌표 확인
    			int dx = cur.X + dx[i];
    			int dy = cur.Y + dy[i];
    			if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue; // 범위 체크
    			if (board[nx][ny] != 1 || vis[nx][ny]) continue; // 방문 했는 지, 현재 값이 1인지 확인
    			vis[nx][ny] = 1; // 방문 체크
    			q.push({nx, ny}) // 해당 좌표를 큐에 저장
    		}
    	}
    }

  • 시작 좌표가 여러 개인 BFS
    BFS의 시작 좌표가 여러 개인 경우, 해당 좌표들을 순서대로 큐에 넣어준다. 큐에서 좌표들이 순서대로 pop, push 되기 때문에, 각 시작 좌표에 따라 순서대로 BFS가 진행된다.