알고리즘/C++
[C++] BAEKJOON 1012 유기농 배추
ssung.k
2019. 10. 1. 23:57
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (
www.acmicpc.net
dfs 를 이용해서 구현하였습니다.
K 번 만큼 받은 좌표를 통해 board 를 완성한 후, 연결되는 구간이 몇 개인지 세주는 문제였습니다.
#include <iostream>
using namespace std;
int board[50][50];
int cnt;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int y,int x, int M, int N){
board[y][x] = 0;
for (int i=0;i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (0<=nx && nx<M && 0<= ny && ny<N){
if (board[ny][nx]){
dfs(ny,nx,M,N);
}
}
}
}
void init(int M, int N){
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
board[i][j] = 0;
}
}
}
int main(int argc, const char * argv[]) {
int T;
cin >> T;
while (T--){
// M : 가로, N : 세로
int M,N,K;
cin >> M >> N >> K;
init(M,N);
for (int i=0;i<K;i++){
int x,y;
cin >> x >> y;
board[y][x] = 1;
}
cnt = 0;
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
if (board[i][j]){
cnt++;
dfs(i,j,M,N);
}
}
}
cout << cnt << "\n";
}
return 0;;
}