[백준알고리즘-JAVA]1012번 풀이(유기농 배추) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1012번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1012(유기농 배추)

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추 흰 지렁이를 구입하기로 결심한다. 이 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추 흰 지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

 

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추 흰 지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추 흰 지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로 길이 N(1N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그다음 KK 줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추 흰 지렁이 마리 수를 출력한다.

입력, 출력 예시

성공코드

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

public class Main {

	static boolean[][] check;
	static int[][] arr;

	static int count = 0, ans = 0;
	
	static int T, M, N, K;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		T = Integer.parseInt(br.readLine());
		
		for(;T-- > 0;) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			arr = new int[N+1][M+1];
			check = new boolean[N+1][M+1];
			
			for(int i = 0 ; i < K ; i++) {
				StringTokenizer temp = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(temp.nextToken());
				int y = Integer.parseInt(temp.nextToken());
				
				arr[y+1][x+1] = 1;
			}
			
			for(int i = 1 ; i <= N ; i++) {
				for(int j = 1 ; j <= M ; j++) {
					dfs(i,j);
					if(count != 0) {
						ans++;
						count = 0;
					}
				}
			}
			sb.append(ans + "\n");
			count = 0;
			ans = 0;
		}
			System.out.println(sb);
		}
	public static void dfs(int a, int b) {
		
		if(!check[a][b]) {
			check[a][b] = true;
			
			if(arr[a][b] == 1) {
				count++;
			
			if( a < N && b < M) {
			if(arr[a+1][b] == 1) dfs(a+1,b);
			if(arr[a-1][b] == 1) dfs(a-1,b);
			if(arr[a][b+1] == 1) dfs(a,b+1);
			if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a < N && b >= M) {
				if(arr[a+1][b] == 1) dfs(a+1,b);
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a >= N && b < M) {
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b+1] == 1) dfs(a,b+1);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}
			else return;
			
			}
		}
		return;
	}
}

이번 문제의 기본적인 해결책은 이전에 풀어보았던 단지 번호 붙이기와 똑같습니다. 1을 인지하고 동서남북으로 방문하지 않았고 1의 값을 가지고 있으면 check 하면 됩니다. 여기서 단, 우리가 알아야 하는 것은 바로 지렁의 이 개수 단지 붙이기로 본다면 단지의 개수 즉, ar의 크기만 돌려주면 되는 문제입니다.

[백준알고리즘-JAVA]2667번 풀이(단지번호붙이기) - 초보도 이해하는 풀이

 

STEP을 따라가며 이해해 보도록 하죠

---

알고리즘 흐름도

 입력받기 -> arr, check 배열 만들기 -> 동서남북 방문하기 -> 개수 카운트하기 -> 출력하기

---

STEP1 입력받고 arr, check 배열 만들기

M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			arr = new int[N+1][M+1];
			check = new boolean[N+1][M+1];
			
			for(int i = 0 ; i < K ; i++) {
				StringTokenizer temp = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(temp.nextToken());
				int y = Integer.parseInt(temp.nextToken());
				
				arr[y+1][x+1] = 1;
			}

이건 뭐 크게 알려드릴 것도 없습니다. 여기서 생각해볼 점이 왜 arr, check 배열 +1을 했느냐? 이 의문에 대해서 이해하셔야 합니다. (꼭 +1이 필요하지는 않습니다. N, M으로 선언해도 더 쉽게 풀이할 수도 있습니다!)

 

정확한 이유는 바로 저희가 찾으려는 인덱스를 넘어가지 않게 하기 위해서 추가의 행과 열을 더하여 -로 가는 것을 방지하기 위함입니다! 쉽게 말해서 그냥 인덱스를 넘어가지 않게 하기 위해 만든 가상의 선입니다.

---

STEP2 DFS 구현하기

	public static void dfs(int a, int b) {
		
		if(!check[a][b]) {
			check[a][b] = true;
			
			if(arr[a][b] == 1) {
				count++;
			if( a < N && b < M) {
			if(arr[a+1][b] == 1) dfs(a+1,b);
			if(arr[a-1][b] == 1) dfs(a-1,b);
			if(arr[a][b+1] == 1) dfs(a,b+1);
			if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a < N && b >= M) {
				if(arr[a+1][b] == 1) dfs(a+1,b);
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a >= N && b < M) {
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b+1] == 1) dfs(a,b+1);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}
			else return;
			}
		}
		return;
	}

 크게 어렵지 않습니다. 이전 글 단지 번호 붙이기와 거의 유사합니다. 

 

 - 방문했는지 안 했는지 확인

 - 안 했다면 check [a][b]=true 실행 (이제는 방문했다는 의미)

 - 만약 해당 위치 값이 1이라면 count를 증가

 - 또 if elseif elseif는 인덱스 범위가 넘어가는지 확인

 - 만약 인덱스 범위가 N M 모두 안 넘거나 N만 넘거나 M만 넘거나 3가지를 고려하여 dfs 재실행

 - 만약 1이 아니라면 종료

 

이런 형식으로 진행되는 dfs를 만드시면 됩니다.  dfs를 풀어보면서 재귀를 구현할 때마다 드는 생각이지만, 동적 계획법과 굉장히 유사해 보이기도 하다.

---

STEP 3 dfs 활용하기

			for(int i = 1 ; i <= N ; i++) {
				for(int j = 1 ; j <= M ; j++) {
					dfs(i,j);
					if(count != 0) {
						ans++;
						count = 0;
					}
				}
			}
			
			sb.append(ans + "\n");
			count = 0;
			ans = 0;

자 간단하죠 2중 for문을 통해서 dfs를 실행 실행 후 count가 0이 아니라면 ans++하고 다시 count는 0으로 초기화

 

맨 뒤 3줄은 T-- > 0에 관한 식! 또 다른 행렬을 입력받기 위해 초기화해주는 모습