💡문제 분석 요약

해충으로부터 배추를 보호하기 위해 배추흰지렁이를 키움

어떤 배추에 배추흰지렁이가 한 마리라도 있으면, 이 지렁이는 인접한 배추로 이동 가능 & 해충으로부터 보호됨

한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우 서로 인접한 것.

<aside> 🔖 예

0: 배추 심어져 있지 않은 땅, 1: 배추 심어져 있는 땅

아래의 배추밭의 경우 최소 5마리의 배추흰지렁이 필요

입력

첫째 줄 : 테스트 케이스 개수 T

둘째 줄 ~ T개: 테스트 케이스

• 첫째 줄 : 배추를 심은 배추밭의 가로 길이 M, 세로 길이 N, 배추가 심어져 있는 위치의 개수 K
  • 1 ≤ M ≤ 50, 1 ≤ N ≤ 50, 1 ≤ K ≤ 2500
• K개의 줄 : 배추의 위치 X, Y가 주어짐
  • 0 ≤ X ≤ M - 1, 0 ≤ Y ≤ N - 1
  • 두 배추의 위치가 같을 수 없음

출력

각 테스트 케이스에 대해 필요한 최소 배추흰지렁이 수

• 예제

<aside> 📎 https://www.acmicpc.net/problem/1012

</aside>

💡알고리즘 설계

1. M X N 배열 초기화
2. DFS 알고리즘으로 탐색
   1. 행렬값 1인 경우 상하좌우 배추 방문
   2. 방문 완료한 위치에 대해서 행렬값 0으로 바꾸기
3. 모든 배추 위치 방문하면서 인접 구역 개수 세기