[BaekJoon] 1012 유기농 배추

1.  문제 링크

2.  문제

요약

• 유기농 배추를 재배하는데 배추를 해충으로부터 보호하는 것이 중요하므로 배추흰지렁이를 구입합니다.
• 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있다면 인접한 배추로 이동할 수 있어 그 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에는 해당 배추들도 해충으로부터 보호받을 수 있습니다.
• 배추들이 군데군데 심어져있는데 해당 배치에서 필요한 배추흰지렁이의 최소수를 구하는 문제입니다.
• 입력
• 첫 번째 줄에는 테스트 케이스의 개수가 주어지고 그 다음 줄부터 각 테스트 케이스에 대해 주어집니다.
• 각 테스트 케이스에는 첫 번째 줄에는 배추밭의 가로길이 M, 세로길이 N, 배추가 심어져 있는 위치의 개수 K가 주어지고 두 번째 줄부터 K개의 줄에는 배추의 위치 X, Y가 주어집니다.
• 출력: 각 테스트 케이스에 대해 최소의 배추흰지렁이 수를 출력합니다.

3.  소스코드

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

public class Main {
	static int count = 0;
	int[][] map;
	int[][] check;
	static int row;
	static int col;
	
	public void dfs(int x, int y) {
		check[x][y] = 1;
		int[] four_directions_x = {0, 0, -1, 1};
		int[] four_directions_y = {-1, 1, 0, 0};
		for(int i = 0; i < 4; i++) {
			int check_x = x + four_directions_x[i];
			int check_y = y + four_directions_y[i];
			if(check_x >= 0 && check_y >= 0 && check_x < row && check_y < col) {
				if(map[check_x][check_y] == 1 && check[check_x][check_y] == 0) {
					dfs(check_x, check_y);
				}
			}
		}
	}
	
	public void makeMap(ArrayList<String> point) {
		map = new int[row][col];
		check = new int[row][col];
		for(int i = 0; i < point.size(); i++) {
			StringTokenizer st = new StringTokenizer(point.get(i));
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			map[x][y] = 1;
		}
	}
	
	public void getMinNum(ArrayList<String> point) {
		makeMap(point);
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				if(map[i][j] == 1 && check[i][j] == 0) {
					count++;
					dfs(i, j);
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int case_num = Integer.parseInt(br.readLine());
		int[] result = new int[case_num];
		for(int i = 0; i < case_num; i++) {
			String case_str = br.readLine();
			StringTokenizer st = new StringTokenizer(case_str);
			col = Integer.parseInt(st.nextToken());
			row = Integer.parseInt(st.nextToken());
			int num = Integer.parseInt(st.nextToken());
			ArrayList<String> point = new ArrayList<String>();
			for(int j = 0; j < num; j++) {
				point.add(br.readLine());
			}
			Main m = new Main();
			m.getMinNum(point);
			result[i] = count;
			count = 0;
		}
		br.close();
		for(int i = 0; i < result.length; i++) {
			bw.write(result[i] + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• (0, 0)부터 시작하여 해당 위치 상하좌우 네 방향에 배추가 존재하는지 확인하여 존재하는 곳을 찾아 해당 지역에 배추흰지렁이 한 마리를 배치합니다.
• 이를 배추밭 전지역에 모두 진행하여 배추흰지렁이의 마리 수를 구하면 됩니다.

1. 배추가 심어져있는 위치를 토대로 2차원 배열로 배추밭을 형성하고 각 지역이 체크되었는지 확인하기 위해 같은 크기의 2차원 배열을 하나 더 만듭니다.
2. (0, 0)부터 가로로 배추밭을 확인하고 만약 해당 위치에 배추가 심어져있고 그 위치를 확인하지 않았다면 배추흰지렁이의 마리 수를 1 증가시키고 해당 위치를 확인한 것이므로 체크되었는지 확인하기 위한 2차원 배열의 해당 위치의 값을 변경하며 DFS를 이용하여 인접된 배추들을 확인합니다.
3. DFS를 이용하기 때문에 해당 위치에서 상하좌우를 확인하고 만약 인접된 배추가 존재하는 곳을 찾았다면 체크되었는지 확인하기 위한 2차원 배열의 해당 위치의 값을 변경하고 해당 위치에서 다시 DFS를 이용하여 상하좌우를 확인하고 인접된 배추가 있는지 확인합니다.
4. 더 이상 인접된 배추가 없는 곳이라면 다시 바로 전으로 돌아가 그 위치에서 다른 방향을 확인하고 인접된 배추가 있다면 3번을 반복합니다.
5. 더 이상 가장 상위 위치까지 모든 방향에서 인접된 배추가 없거나 모두 확인된 곳이라면 가로 방향의 다음 위치로 넘어갑니다.
6. 2번부터 5번 방식을 모든 배추밭을 확인할 때까지 진행합니다.