[백준 1012번] 유기농 배추

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

1012번: 유기농 배추

이 문제는 그래프 탐색을 이용해서 푸는 문제입니다.

---

해결법

 

m*n 크기의 밭에 있는 배추들이 인접해있으면 인접해있는 배추들의 수와 관계없이 하나의 지렁이만 있으면 되는 내용입니다.  한마디로, 인접해있는 노드들의 집합 개수만 세면 되는 문제죠. 그러기 떄문에 해결법은

1. 이중 for문을 통해 값이 1인 밭을 찾는다.
2. 찾았다면, y방향으로 -1, 1, x방향으로 -1 1를 각각 이동하면서 값이 1인 밭을 찾는다. 
3.단 방문할때마다. 그 값을 0으로 바꿔준다. 
4.다 방문하였다면 count를 1해주고 다시 이중 for문을 이용 끝까지 탐색한다.

 

코드

 

import java.util.*;
import java.io.*;
public class Main {
	static int count=0;
	//방향설정
	static int[] strX= {0,0,-1,1};
	static int[] strY= {-1,1,0,0};
	public static void main(String arg[]) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		
		for(int i=0;i<T;i++) {
			int x=0;
			int y=0;
			int m=sc.nextInt();
			int n=sc.nextInt();
			int k=sc.nextInt();
			int [][]field=new int[m][n];
			
			for(int j=0;j<k;j++) {
				x=sc.nextInt();
				y=sc.nextInt();
				field[x][y]=1;
			}
			sol(field,m,n);
			System.out.println(count);
			count=0;
		}
		
	}
	public static void counting_cabbage(int[][]field,int x,int y,int m,int n) {
		for(int i=0;i<4;i++) {
			if((x+strX[i]>=0&&x+strX[i]<m)&&((y+strY[i]>=0&&y+strY[i]<n))) {
				if(field[x+strX[i]][y+strY[i]]==1) {
					field[x+strX[i]][y+strY[i]]=0;
					counting_cabbage(field,x+strX[i],y+strY[i],m,n);
				}
			}
		}
		return;
	}
	public static void sol(int [][]field,int m,int n) {
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(field[i][j]==1) {
					count++;
					counting_cabbage(field,i,j,m,n);
				}
			}
		}
	}
}