반응형
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include <iostream> #include <queue> #include <cstring> #define rep(i,n) for(int i=0;i<n;i++) #define pii pair<int, int> using namespace std; int t, m, n, k, cnt; int arr[51][51]; bool visited[51][51]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void bfs(int x, int y) { // bfs 실행할 때마다 cnt++ cnt++; queue<pii> q; q.push({ x, y }); visited[x][y] = true; while (!q.empty()) { pii now = q.front(); q.pop(); int x = now.first; int y = now.second; rep(i, 4) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m) { if (arr[nx][ny]==1 && !visited[nx][ny]) { visited[nx][ny] = true; q.push({ nx,ny }); } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> t; while (t--) { cnt = 0; memset(arr, 0, sizeof(arr)); memset(visited, 0, sizeof(visited)); cin >> m >> n >> k; rep(i, k) { int a, b; cin >> a >> b; arr[b][a] = 1; } rep(i,n){ rep(j, m) { // 현재 1이고 방문 안했으면 bfs if (arr[i][j] == 1 && !visited[i][j]) bfs(i, j); } } cout << cnt << '\n'; } } | cs |
반응형