[백준]1012번 유기농 배추(JAVA)

0. 문제 링크

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

1012번: 유기농 배추

 

1. 문제 설명

1) M*N 크기의 배추밭에 살아야 하는 배추흰지렁이의 마리 수 구하기

 

2. 입출력

// input
2 // 테스트 케이스의 개수
10 8 17 // M, N, K(배추의 위치)
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
5
1

 

3. 코드

import java.util.*;
import java.awt.Point;
import java.io.*;

public class b1012 {
	private static int M;
	private static int N;
	private static int K;
	private static int[][] map;
	private static boolean[][] visited;
	private static int[] dr = {0, 1, 0, -1};
	private static int[] dc = {1, 0, -1, 0};
	private static int ans;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		
		for(int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken()); // 가로
			N = Integer.parseInt(st.nextToken()); // 세로
			K = Integer.parseInt(st.nextToken()); // 배추의 개수
			map = new int[M][N]; // 땅
			visited = new boolean[M][N]; // 방문 여부
			for(int k = 0; k < K; k++) {
				st = new StringTokenizer(br.readLine());
				int r = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				map[r][c] = 1; // 배추 심기
			}
			ans = 0; // 흰지렁이 개수
			
			for(int i = 0; i < M; i++) {
				for(int j = 0; j < N; j++) {
					if(map[i][j] == 1 && !visited[i][j]) { // 배추가 심어져 있고, 방문 전이면
						dfs(i, j); // dfs로 탐색
//						bfs(i, j); // bfs로 탐색
						ans++; // 흰지렁이 한 마리 추가
					}
				}
			}
			
			System.out.println(ans); // 출력
		}
	}

	private static void dfs(int r, int c) {
		// inductive part
		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr >= 0 && nr < M && nc >= 0 && nc < N && map[nr][nc] == 1) { // 범위 내에 배추가 있으면
				if(!visited[nr][nc]) { // 방문 전이면
					visited[nr][nc] = true; // 방문 처리
					dfs(nr, nc); // 이어서 방문
				}
			}
		}
		
	}

	private static void bfs(int r, int c) {
		Queue<Point> Q = new LinkedList();
		Q.add(new Point(r, c)); // 큐에 넣고
		visited[r][c] = true; // 방문 처리
		
		while(!Q.isEmpty()) {
			Point p = Q.poll();
			for (int d = 0; d < 4; d++) {
				int nr = p.x + dr[d];
				int nc = p.y + dc[d];
				if(nr >= 0 && nr < M && nc >= 0 && nc < N && map[nr][nc] == 1 && !visited[nr][nc]) {
					visited[nr][nc] = true;
					Q.add(new Point(nr, nc));
				}
			}
		}
	}

}

 

실행 결과

 

4. 회고

1) 배추밭에 배추가 심어져 있으면 dfs/bfs로 탐색 후 흰지렁이의 개수를 추가함

-> dfs/bfs를 통해 인접한 배추를 방문 처리함

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b1012.java