[백준 BOJ][dfs] 1012 유기농 배추

1012_유기농 배추

링크

https://www.acmicpc.net/problem/1012

 

풀이

 

문제는 최소의 배추흰지렁이 마리 수를 요구합니다.

배추흰지렁이는 상하좌우 네 방향으로만 생각해야하기 때문에 dx배열과 dy배열을 만들어줍니다.

 

땅을 배열로 표현한 다음 배추가 있는 곳을 1이라 해놓고 dfs를 돌리면 풀 수 있습니다.

 

코드

 

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

//1012_유기농 배추 #include <cstdio> #include <string.h> using namespace std;   int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; int arr[52][52]; int T, n, m, k, ans;   void dfs(int x, int y) {     arr[x][y] = 0;     for (int i = 0; i < 4; ++i) {         if (arr[x + dx[i]][y + dy[i]])             dfs(x + dx[i], y + dy[i]);     } }   int main() {     scanf("%d", &T);          while (T--) {         memset(arr, 0, sizeof(arr)), ans = 0;        //초기화         scanf("%d %d %d", &m, &n, &k);           for (int i = 0; i < k; ++i) {             int x, y;             scanf("%d %d", &x, &y);               arr[++x][++y] = 1;         }           for (int i = 1; i <= m; ++i) {        //m이 가로, x, i             for (int j = 1; j <= n; ++j) {    //n이 세로, y, j                 if (arr[i][j]) ans++, dfs(i, j);             }         }           printf("%d\n", ans);     }       return 0; } Colored by Color Scripter

cs