백준 1012 유기농 배추 (자바)

dfs를 이용하여 풀 수 있고, bfs로도 풀 수 있습니다. 이 문제는 배추가 심어진 곳을 기준으로 주위의 배추들을 없애버리면 됩니다. 무슨 말인지 아직은 모르실겁니다.

 

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

1012번: 유기농 배추

이 문제의 핵심은 빨간색을 제외하고 그 인접한 곳을 모두 0으로 바꿔버리면 됩니다. 즉 모여있는 배추중에 하나만 선택한다는 것인데요 그래야 지렁이의 갯수를 알 수 있습니다. 

 

이것을 알고리즘으로 구현하시면 되는데 방법은 많습니다. 하지만, 무조건 배추무리에 하나만 빼고 다 지워야 하고, 그걸 어떻게 표현하는지는 본인 몫입니다. 

 

다른 블로그를 보니 어떤 분은 이중 for문을 이용해서 기준 배추발견하면 그 배추를 중심으로 나머지 배추들을 방문처리 시킴으로써 구현 하셨습니다. 

 

저는 아래와 같이 배추가 심어져 있다(land[i]=1)이라면 depth를 기준으로 기준 배추와 나머지 배추를 따로 처리했습니다. 

 

package al4;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int t,m,n,k;
	static int a,b;
	static int sum;
	static int[][] land;
	static int[][] visit;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		t = Integer.parseInt(br.readLine());

		for(int tc=0; tc<t; tc++)
		{
			st = new StringTokenizer(br.readLine()," ");
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
		
			land = new int[n][m];
			visit = new int[n][m];
			
			sum = 0;
			
			for(int i=0; i<k; i++)
			{
				st = new StringTokenizer(br.readLine()," ");
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				
				land[b][a] = 1;
			}
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					dfs(i,j,0);
				}
			}

			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					sum += land[i][j];
				}
			}
			bw.write(sum+"\n");
		}
		
		bw.flush();
		br.close();
		bw.close();
	}
	
	static void dfs(int c, int d, int depth) {
		
		if(c>=n||d>=m||c<0||d<0)return;
		if(visit[c][d]==1)return;
		visit[c][d] = 1;
		
		if(land[c][d] == 1) {
			if(depth!=0) {
				land[c][d] = 0;
			}
			dfs(c+1,d,depth+1);
			dfs(c-1,d,depth+1);
			dfs(c,d-1,depth+1);
			dfs(c,d+1,depth+1);
		}
		else if(land[c][d]==0) {
			return;
		}
	}

}