[백준] 1012번: 유기농 배추 풀이 및 해설(C++)

 

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

1012번: 유기농 배추

 

C++로 작성한 백준 문제 1012번 유기농 배추에 대한 문제 풀이다.

실버 2 문제로 그래프 이론, 그래프 탐색, 너비우선탐색, 깊이우선탐색이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추 흰 지렁이를 구입하기로 결심한다. 이 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추 흰 지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해 있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해 있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추 흰 지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그다음 K 줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

 

---

문제 파악하기

1. 결국 문제를 요약하면 총 몇개의 조각으로 이루어져 있는가?이다.
2. 가로세로 칸이 주어져 있으니 이차원 배열을 사용하여 표현하면 된다.
3. 2차원 배열의 인덱스 2개 중 1개라도 같다면 인접한 것이다.

 

 

 

 

 

---

 

코드 및 설명

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

    int cnt=0,repeat,a,b,worm;
    int arr[51][51];
    bool visited[51][51]={false};
    
void dfs(int i,int j){
        if(j>0){
            if(arr[i][j-1]==1 && !visited[i][j-1]){
                visited[i][j-1]=true;

                dfs(i,j-1);
            }
        }
        if(j<b-1){
            if(arr[i][j+1]==1 && !visited[i][j+1]){
                visited[i][j+1]=true;

                dfs(i,j+1);
            }
        }
    
        if(i>0){
            if(arr[i-1][j]==1 && !visited[i-1][j]){
                visited[i-1][j]=true;

                dfs(i-1,j);
            }
        }
        if(i<a-1){
            if(arr[i+1][j]==1 && !visited[i+1][j]){
                visited[i+1][j]=true;

                dfs(i+1,j);
            }
        }
    

}    


int main(){
    cin>>repeat;
    for(int k=0; k<repeat; k++){
        cin>>a>>b>>worm;
    for(int i=0; i<worm;i++){
        int x,y;
        cin>>x>>y;
        arr[x][y]=1;
    }
    for(int i=0; i<a;i++){
        for(int j=0; j<b; j++){
            if(arr[i][j]==1 && !visited[i][j]){
                visited[i][j]=true;
                cnt++;
                dfs(i,j);
            }
        }
        
    }
    cout<<cnt<<'\n';
    cnt=0;
    for(int i=0; i<51; i++){
        for(int j=0; j<51; j++){
            arr[i][j]=false;
            visited[i][j]=false;
        }
    }

}
}

 

DFS나 BFS 알고리즘을 이용해 인접해 있는지를 판단하면 된다.

0이 나오면 패스하고, 1이 나오면 DFS나 BFS로 탐색하고, 탐색한 곳에는 이미 탐색했다고 흔적을 남긴다.

탐색이 끝나면 답 개수를 1 올려준다.

 

---

 

헤매었던 부분

질문을 여러 번 하는데 배열 리셋을 안 해서 1번 틀렸다.

 

 

 

 

 

---

 

마무리

BFS보단 DFS를 좋아해서 DFS로 했지만 BFS로 풀어도 상관없는 문제다.