백준 1012 유기농 배추

문제 링크 : https://www.acmicpc.net/problem/1012

※선행해야 할 알고리즘 : BFS/DFS

Algorithm : BFS/DFS 를 활용하여 군집을 찾아 군집의 개수를 출력해라

1. 입력받은 m, n, k를 통해 그래프를 만든다

2. 그래프에서 1이 입력된 인덱스를 찾아 반환한다.

3. 반환된 인덱스를 기준으로 아래, 왼쪽, 오른쪽을 BFS하며 count 한다. 이 때, 1을 찾아 방문을 했기에 count의 초기값은 1이다. 또한 방문한 곳들은 그래프를 0으로 설정하여 다시 들리지 못하게 한다.

4. 1~3을 그래프에 1이 더 이상 없을 때까지 반복하여 count된 군집 개수를 반환한다.

5. 1~4를 queue를 활용하여 T번 반복하여 BFS를 진행하면 다음과 같다.

#include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; int m, n, k; pair<int, int> search(vector<vector<int>> G) { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (G[i][j]) return { i,j }; return { -1,-1 }; } int sol(vector<vector<int>> G) { int result = 0; while (1)  { queue < pair<int, int>> q; auto s = search(G); if (s.first == -1 && s.second == -1) break; else q.push(s); while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); G[y][x] = 0; for (int i = 0; i < 4; i++) { int now_y = y + dy[i]; int now_x = x + dx[i]; if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < m && G[now_y][now_x]) { q.push({ now_y, now_x }); G[now_y][now_x] = 0; } } } result++; } return result; } int main() { int T; cin >> T; vector<int> result; for (int z = 0; z < T; z++) { cin >> m >> n >> k; //vector초기화 vector<vector<int>> G(n); for (int i = 0; i < n; i++) G[i].resize(m, 0); for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; G[y][x] = 1; } result.push_back(sol(G)); } for (int i = 0; i < result.size(); i++) cout << result[i] << endl; }