[실버2] 1012. 유기농 배추 (Java)

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

1012번: 유기농 배추

양배추 - 눈물샤워

---

※  문제를 요약하면 아래와 같습니다.

▶ 가로가 M 세로가 N인 크기의 지도에서 K개의 배추가 존재

▶  해충을 잡기위해 지렁이를 배치

▶  지렁이는 상하좌우에 배추가 존재 시 이동하며 해충들 섭취

▶  최소로 필요한 지렁이 수

▶  Input : 첫째 줄에 testcase 횟수, 다음 줄에 M, N, K가 공백으로 구분되어 주어지고, K줄만큼 배추의 좌표 (가로,세로) 

▶  Output : testcase별 최소 지렁이 수 출력

---

◈ Input - 1

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

◈ Output - 1

5
1

◈ Input - 2

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

◈ Output - 2

2

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 최소 지렁이 수 == DFS 횟수

▶ map으로 입력 받을 때 boolean 2차원 배열로 저장하여 1일 경우 true로 저장

▶ DFS를 재귀형태로 구현, 주어진 map 배열에서 각 좌표 별로 상,하,좌,우를 탐색하여 1일 경우 계속 탐색

▶ 상하좌우 탐색은 델타로 구현

▶ 탐색 시 방문처리 필수

▶ DFS 종료 할 때마다 지렁이 1씩 카운트

---

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

public class Main {
	static boolean[][] barrVisited;
	static boolean[][] barrFarm;

	// 동서 남북
	static int[] dr = { 0, 0, 1, -1 };
	static int[] dc = { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {

		// 대박 대박 대박
		System.setIn(new FileInputStream(Main.class.getResource("input.txt").getPath()));

		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(bReader.readLine());

		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());

			int M = Integer.parseInt(st.nextToken()); // cols
			int N = Integer.parseInt(st.nextToken()); // rows
			int K = Integer.parseInt(st.nextToken()); // cabbage count

			barrVisited = new boolean[N][M];
			barrFarm = new boolean[N][M];

			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(bReader.readLine());
				int nCol = Integer.parseInt(st.nextToken());
				int nRow = Integer.parseInt(st.nextToken());

				barrFarm[nRow][nCol] = true;
			}

			int nWarm = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (barrFarm[i][j] && !barrVisited[i][j]) {
						DFS(i, j);
						nWarm++;
					}
				}
			}

			bWriter.write(nWarm + "\n");
			bWriter.flush();
		}
		bWriter.close();
	}

	public static void DFS(int nRow, int nCol) {
		// 기저 조건
		if (barrVisited[nRow][nCol])
			return;

		// 탐색 조건
		barrVisited[nRow][nCol] = true;
		for (int k = 0; k < dr.length; k++) {
			int nRowSearch = nRow + dr[k];
			int nColSearch = nCol + dc[k];

			// 동, 서, 남, 북 중 배추가 있다
			if (nRowSearch >= 0 && nColSearch >= 0 && nRowSearch < barrFarm.length && nColSearch < barrFarm[0].length
					&& barrFarm[nRowSearch][nColSearch])
				DFS(nRowSearch, nColSearch);
		}
	}
}

 

Good Luck! (피드백 감사합니다!)