[백준/자바] 1012번: 유기농 배추

문제

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

풀이

• 배추를 해충으로부터 보호하기 위해 배추흰지렁이를 구입하기로 함
• 지렁이는 배추 근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호함
• 어떤 배추에 지렁이가 살고 있으면 상하좌우 인접한 배추를 보호함
• 2차원 공간에 배추를 심었다고 했을 때, 필요한 배추흰지렁이의 최솟값 출력

전형적인 그래프 탐색 문제입니다.
BFS를 사용해 풀어봤습니다.

			visited = new boolean[n][m];
			int answer = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (map[i][j] && !visited[i][j]) {
						bfs(i, j);
						answer++;
					}
				}
			}

• 입력을 받은 후 2중 for문을 사용해 "배추가 존재"하며 "방문하지 않은 좌표"일 경우에 탐색을 진행했습니다.
• 탐색을 진행할 때마다 배추흰지렁이의 수를 증가시켰습니다.

	private static void bfs(int sr, int sc) {
		visited[sr][sc] = true; // 시작 좌표 방문 처리
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {sr, sc}); // 큐에 삽입
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1]; // 탐색할 좌표값
			
			for (int i = 0; i < 4; i++) { // 4방 탐색
				int nr = r + dr[i];
				int nc = c + dc[i];
				
                // 범위 밖이거나 배추가 아니거나 이미 방문한 좌표라면 pass
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || !map[nr][nc] || visited[nr][nc]) continue;
				
                // 아니라면 큐에 삽입 및 방문 처리
				queue.add(new int[] {nr, nc});
				visited[nr][nc] = true;
			}
		}
	}

• 전형적인 BFS 코드입니다.
• 범위 내에 존재하며 방문하지 않은 배추 좌표일 경우에만 queue에 삽입하면 됩니다.

코드

import java.util.*;
import java.io.*;

public class Main_1012 {
	static StringBuilder sb = new StringBuilder();
	static int m, n, k;
	static boolean[][] map, visited;
	
	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	
	private static void bfs(int sr, int sc) {
		visited[sr][sc] = true;
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {sr, sc});
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || !map[nr][nc] || visited[nr][nc]) continue;
				
				queue.add(new int[] {nr, nc});
				visited[nr][nc] = true;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < t; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			
			map = new boolean[n][m];
			for (int i = 0; i < k; i++) {
				st = new StringTokenizer(br.readLine());
				int c = Integer.parseInt(st.nextToken());
				int r = Integer.parseInt(st.nextToken());
				map[r][c] = true;
			}
			
			visited = new boolean[n][m];
			int answer = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (map[i][j] && !visited[i][j]) {
						bfs(i, j);
						answer++;
					}
				}
			}
			sb.append(answer).append('\n');
		}
		System.out.println(sb.toString());
	}

}