[백준] 1012번 : 유기농 배추 [C/C++]

#문제

1012번: 유기농 배추

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

1012번: 유기농 배추

 

---

#접근방법

그래프 탐색 기법 중 깊이우선탐색(dfs)를 사용하여 접근하였다.

반응형

---

#풀이

#include <stdio.h>
#include <memory.h>

int arr[55][55]={0};
int xx[4] = {0,0,-1,1};
int yy[4] = {1,-1,0,0};
int t,m,n,k;
int a,b;
int ans;

void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int X = x+xx[i];
        int Y = y+yy[i];

        if(X>=0 && X<n && Y>=0 && Y<m && arr[X][Y]==1){
            arr[X][Y] = 0;
            dfs(X,Y);
        }
    }

    return;
}

int main(){
    scanf("%d",&t);

    while(t--){
        ans = 0;

        scanf("%d %d %d",&m,&n,&k);

        for(int i=0;i<n;i++)
            memset(arr[i],0,m*sizeof(int));

        for(int i=0;i<k;i++){
            scanf("%d %d",&a,&b);
            arr[b][a] = 1;
        }

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(arr[i][j]==1){
                    dfs(i,j);
                    ans++;
                }

        printf("%d\n",ans);
    }

    return 0;
}

 

먼저 t를 입력받고 while로 t만큼 반복문을 돌아주면서 m,n,k를 입력받는다.

 

그리고 반복문을 돌면서 memset 함수로 arr배열을 0으로 초기화 해준다. memset함수는 memory.h 헤더파일에 있다.

 

k번 만큼 반복문을 돌면서 a,b을 입력받아 arr배열에 저장해준다.

 

그리고 arr배열 전체를 탐색하면서 만약 arr[i][j]==1 이면 dfs(i,j)를 호출하면서 ans++를 해준다.

 

dfs함수에서 xx, yy배열을 방향벡터로 잡아서 상, 하, 좌, 우 방향을 탐색하면서 범위안에서 arr[X][Y]==1이면 arr[X][Y]를 0으로 만들고 dfs(X,Y)를 호출한다.

 

그러면 인접한 배추를 다 0으로 만들게 되고 이 행동이 ans를 1 증가 시키게 되는 것이다.

 

따라서 while문를 돌 동안 ans를 출력하면 정답이다.

---

#성능

---

#정리

그래프 탐색 기법 중 깊이우선탐색(dfs) 또는 너비우선탐색(bfs)를 아는 것,

 

이를 구현할 수 있으면 풀 수 있는 문제였다.