문제링크
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (
www.acmicpc.net
섬의 개수를 확인하는 방식으로 전형적인 bfs를 사용해서 풀이가 가능하다.
bfs 함수가 실행되는 횟수를 확인하면 된다.
방문하지 않았으면서 배추가 있는 곳이 bfs의 시작점이 된다.
범위 밖을 나가는 요소와 이미 방문한 지점, 방문할 필요가 없는 지점을 제외하면 되는 간단한 bfs이다.
#include<iostream>
#include<queue>
using namespace std;
int map[51][51], vis[51][51];
int m, n, k;
int cnt = 0;
queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
void bfs(pair<int, int> start) { //전형적인 bfs
cnt++; //섬 개수 추가
q.push(start);
vis[start.first][start.second] = 1;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
//범위 나가거나 배추가 없는 곳이거나 이미 방문한 곳이면 continue
if (nr < 0 || nc < 0 || nr >= n || nc >= m || vis[nr][nc] == 1 || map[nr][nc] == 0)continue;
q.push({ nr, nc });
vis[nr][nc] = 1;
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
cin >> m >> n >> k;
int n1, n2;
while (k--) {
cin >> n1 >> n2;
map[n2][n1] = 1;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (map[i][j] == 1 && vis[i][j] == 0)
bfs({ i, j }); //1인 지점 넘겨줘야함
cout << cnt << '\n';
//이후로 초기화
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
map[i][j] = 0;
vis[i][j] = 0;
}
cnt = 0;
}
return 0;
}