본문 바로가기
라이브러리/그래프

BFS

by 유시은 2020. 12. 13.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int R, C;
int board[100][100];
int dir8[2][8]{ {0, -1, 0, 1, -1, -1, 1, 1}, {1, 0, -1, 0, 1, -1, -1, 1} };
bool dup[100][100];

void bfs(pii init) {
	int cr, cc, nr, nc;
	queue<pii> que; dup[init.first][init.second] = true;
	for (que.push(init); !que.empty(); que.pop()) {
		tie(cr, cc) = que.front();
		for (int i = 0; i < 4; ++i) {
			nr = cr + dir8[0][i], nc = cc + dir8[1][i];
			if (nr < 0 || nc < 0 || nr >= R || nc >= C || dup[nr][nc] || board[nr][nc] == 0) continue; dup[nr][nc] = true;
			que.push({ nr, nc });
		}
	}
}

int main() {
	int res = 0;
	cin >> R >> C;
	for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) cin >> board[r][c];
	for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) if (!dup[r][c] && board[r][c] == 1) bfs({ r, c }), res++;
	cout << res;
}

 

복붙용

'라이브러리 > 그래프' 카테고리의 다른 글

BFS  (0) 2020.12.13
Topological Sort  (0) 2020.09.16
Dijkstra  (0) 2020.08.06
Tree  (0) 2020.08.06

댓글0