[BaekJoon] 백준 1012번 _ 유기농 배추 for JAVA _ DFS 알고리즘

 

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

1012번: 유기농 배추

 

 

 

문제

 

 

 

---

 

얘도 그냥 전형적인 DFS/BFS 문제이다.

 

 

 

DFS 연습중이라 DFS로 풀음

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Baek1012 { // DFS
	public static int count[] = new int[1250];  //50x50 밭에 지렁이는 최대 1250개라 1250으로 했다.
	public static int farm[][] = new int[50][50];
	public static int M = 0, N = 0, K = 0;
	public static int index = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				M = Integer.parseInt(st.nextToken());
				N = Integer.parseInt(st.nextToken());
				K = Integer.parseInt(st.nextToken());
			
			for(int j = 0; j < K; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				farm[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;	
			}
			
			for(int x = 0; x < M; x++)
				for(int y = 0; y < N; y++) {
					if(worm_DFS(x, y))
						count[index]++;
				}
			
			index++;
		}
		
		for(int i = 0; i < count.length; i++) {
			if(count[i] != 0)
				System.out.println(count[i]);
			else {
				break;
			}
		}
	}
	
	public static boolean worm_DFS(int x, int y) {
		
		if(x <= -1 || y <= -1 || x >= M || y >= N)
			return false;
		
		if(farm[x][y] == 1) {
			farm[x][y] = 0;
			
			//상하좌우 잘펴보기
			worm_DFS(x - 1, y);
			worm_DFS(x + 1, y);
			worm_DFS(x, y + 1);
			worm_DFS(x, y - 1);
			
			return true;
		}
		
		return false;
	}
}

 

 

 

 

 

성능

 

 

 

 

 

아놔 바로 풀었는데 배열 크기 [25][25]로 해서 한번 틀림 킹받아!! 문제 제대로 보자고!!!!!

 

 

 

그리고 여전히 count[]로 출력할 배열을 만들었는데

 

출력할 때 0이 아닐 때만 출력...일케 하는게 먼가 비효율같아서

 

 

다른 방법을 찾아보았다.

 

 

StringBuilder를 사용해보면 좋을듯. sb.append(); 로 넣어서...~ 함 써봐야지~