백준 1012. 유기농 배추(JAVA) (DFS)

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

public class Main {
	
	static int[][] arr;
	static boolean[][]visit;
	static int M,N,K ;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	static int cnt = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < T ; i++) {
			cnt = 0;
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken()); // 가로 길이
			N = Integer.parseInt(st.nextToken()); // 세로 길이
			
			arr = new int[N][M];
			visit = new boolean[N][M];
			
			int K = Integer.parseInt(st.nextToken()); // 배추 개수 
			
			for(int j = 0 ; j < K ; j++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				arr[b][a] = 1;
			}
			
			for(int q = 0 ; q < N; q++) {
				for(int w = 0 ; w < M ; w++) {
					if(arr[q][w] == 1 && !visit[q][w]) {
						dfs(q,w);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}
	}
	
	static void dfs(int x, int y) {
		visit[x][y] = true;
		
		for(int i = 0 ; i < 4; i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];
			
			if(nx >= 0 && ny >= 0 && nx < N && ny < M) {
				if(arr[nx][ny] == 1 && !visit[nx][ny]) {
					dfs(nx,ny);
				}
			}
		}
	}
}

○ 문제 요약

한나는 농약을 사용하기보단 배추흰지렁이를 이용해서 해충으로부터 배추를 보호하려고 한다. 지렁이는 인접한 배추로 이동이 가능하기 때문에 배추가 모여있는 곳을 알면 지렁이가 몇 마리가 필요한지 알 수 있다. 그때 필요한 지렁이의 마리 수를 출력해라. 

○ 문제 풀이

이전 문제들을 풀 때는 가로길이와 세로 길이를 입력받아서 배열에 크기로 정해본 적이 없어서 이번 문제를 푸는데 고생을 했다. 

 

DFS 알고리즘을 사용해서 푼다는 것은 알고 있었기 때문에 추상적으로 이렇게 하면 되겠다는 틀은 잡았지만 구체적으로 메소드를 어떻게 구현해야 할지 막막했다. 그래서 구현하려고 시간을 좀 썼는데 결국 혼자서 못하고 이번에도 도움을 받아서 문제를 해결했다. 언젠가는 혼자서 잘하는 날이 오지 않을까 싶다. 

 

코드를 보면 다 이해할 수 있을 것이기 때문에 DFS 메소드 구현 과정만 설명하도록 하겠다.

먼저 입력 예제 1을 입력받은 상태를 보면 아래 그림과 같다. 

위 그림을 가지고 아래 그림에 대입해보면 

arr[0][0] == 1이고 visit[0][0] 는 현재 방문을 안 했기 때문에 false이므로 조건을 충족해서 dfs(0,0) 실행한다.

 visit[0][0] 는 방문을 한 상태이므로 true를 넣어주고 for문으로 들어가면 

 

for(int i = 0; i < 4; i++){ >> 이 과정은 현재 좌표 상하좌우에 인접한 배추가 있는지 확인하는 과정이라고 보면 된다. 

 int nx = 0 -1 ;

 int ny = 0 + 0;

   if( ..... ) {} >> nx가 0보다 작아서 조건 충족을 못하고 for문으로 돌아간다. 

}

 

for(int i = 1; i < 4 ; i++){ 

 int nx = 0 + 0;

 int ny = 0 + 1;

 if(0 >= 0 && 1 >= 0 && 0 < 8 && 1 < 10) { >> 이번에는 if문 조건을  충족해서 if문을 실행한다.  

  if(arr[0][1] == 1 && visit[0][1] == false){ >> if문 조건 충족해서 dfs(0,1)을 실행한다. 

     dfs(0,1);

  }

 }

}

q가 0이고 w가 0일 때 dfs() 메소드를 재귀 호출해서 노란색 박스 구역을 구하고 cnt = 1이고 되면서 다시 w = 1을 수행하면 (0,1)은 이미 방문한 적이 있기 때문에 w가 M까지 수행한 후에 q가 1이 되고 w가 0이 되면서 같은 과정을 반복한다.

 

배추밭에 있는 각각의 배추가 구성하고 있는 구역의 개수를 알 수 있고 그 구역의 개수만큼 필요한 지렁이의 수도 구할 수 있게 된다.

○ 결과