백준 1012 - 유기농 배추

Java

1012 번 - 유기농 배추

문제

지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.
(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다.
배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.
(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

접근 방법

지도 0,0에서부터 N-1, N-1까지 탐색을 하여, 배추가 존재하면 근처에 있는 모든 배추를 탐색하여 방문 처리를 한다.
한번 방문하였을 때 지렁이 수를 늘려준다.
위 방법으로, 배추가 인접해 있는 붙어있는 배추 그룹의 개수를 구한다.

코드

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

public class Main {
	static int n, m, k, y, x, result;
	static int[][] farm;
	static boolean[][] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	while(tc-- != 0) {
    		stk = new StringTokenizer(br.readLine());
    		n = stoi(stk.nextToken());
    		m = stoi(stk.nextToken());
    		k = stoi(stk.nextToken());
    		
	    	farm = new int[n][m];
	    	visited = new boolean[n][m];
	    	result = 0;	    	
	    	
	    	for(int i = 0; i < k; i++) {
	    		stk = new StringTokenizer(br.readLine());
	    		y = stoi(stk.nextToken());
	    		x = stoi(stk.nextToken());
	    		farm[y][x] = 1;
	    	}
	    	
	    	for(int i = 0; i < n; i++) {
	    		for(int j = 0; j < m; j++) {
					// 0,0 부터 시작하여 N-1,N-1까지 배추가 심어져 있고, 이전 BFS을 통해 방문한 배추가 아니면
	    			if(farm[i][j] == 1 && !visited[i][j]) {
	    				BFS(i,j);
	    			}
	    		}
	    	}
	    	System.out.println(result);
    	}
    	br.close();
	}
	// 상 하 좌 우
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,-1,1};
	
	static void BFS(int yy, int xx) {
		result++;			// 지렁이 수를 늘려줍니다.
		Queue<Pair> q = new LinkedList<>();
		int y, x, ny, nx;
		Pair p;
		q.offer(new Pair(yy,xx));		// 처음 찾은 배추를 넣는다.
		visited[yy][xx] = true;			// 배추를 방문했다고 표현
		while(!q.isEmpty()) {			// 더 이상 방문할 배추가 없을 때까지 
			 p = q.poll();				// 방문 예정인 배추를 하나 가져온다.
			 y = p.y;
			 x = p.x;
			 for(int i = 0; i < 4; i++) {	// 현재 배추의 상하좌우를 탐색한다.
				 ny = y + dy[i];
				 nx = x + dx[i];
				 // 범위를 벗어나지 않고, 처음 방문하였으며 배추가 존재하면
				 if(0 <= ny && ny < n && 0 <= nx && nx < m && !visited[ny][nx] && farm[ny][nx] == 1) {
					 visited[ny][nx] = true;	// 그 배추를 방문 처리한다.
					 q.offer(new Pair(ny,nx));	// 새로운 배추를 넣는다.
				 }
			 }
		}
	}
	
	static class Pair {
		int y, x;
		Pair(int i, int j){
			y = i;
			x = j;
		}
		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append(y).append(", ").append(x);
			return builder.toString();
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐★★★★

후기

이전에도 접했던 문제이기 때문에 쉽게 해결 가능했다.

개선할 점

없