(백준 알고리즘 문제풀이) 1012번 유기농 배추
by 줌코딩
문제
어떻게 접근할 것인가
- 이 문제는 연결된 친구들의 개수를 구해주는 문제이다.
- 따라서 BFS를 이용해서 또는 DFS를 이용해서 풀 수 있다.
- BFS로 노드가 발견될 때까지 진행하고 발견된 노드는 0으로 바꿔주었다.
코드
#include <cstdio>
#include <vector>
#include <queue>
#define pii pair<int, int>
using namespace std;
int t, m, n, k, x, y;
int d[4][2]= { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int main(){
scanf("%d", &t);
while(t--){
int cnt = 0;
queue<pii> q;
scanf("%d %d %d", &m, &n, &k);
vector<vector<int> > v(m, vector<int>(n, 0));;
while(k--){
scanf("%d %d", &x, &y);
v[x][y] = 1;
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(v[i][j] == 1){
q.push(pii(i, j));
v[i][j] = 0;
while(!q.empty()){
int fx = q.front().first, fy = q.front().second;
q.pop();
for(int k = 0; k < 4; k++){
int nx = fx + d[k][0], ny = fy + d[k][1];
if(nx >= m || nx < 0 || ny >= n || ny < 0 || !v[nx][ny])continue;
v[nx][ny] = 0;
q.push(pii(nx, ny));
}
}
cnt++;
}
}
}
printf("%d\n", cnt);
}
}
느낀점
- BFS로 간단하게 끝내버린 문제이다.
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS