[백준] 1012번 유기농 배추

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

 

이 문제는 dfs혹은 bfs로 푸는 문제다.

문제의 요점은 배추밭에 배추지렁이가 최소 몇마리가 필요하냐고 물어보는게 문제다.

즉, 배추밭에 배추 묶음이 몇 묶음이냐라고 말하는 것 과 같다.

위에 1이 모여있는 곳을 세보면

왼쪽 부터 총 5개의 구역으로 나뉜다.

import java.util.*;

class Node {
    int x;
    int y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,-1,1};

    static int[][] makeArray(int M, int N) {
        return new int[N][M];
    }

    static boolean[][] makeBoolArray(int M, int N) {
        return new boolean[N][M];
    }

    static List<Integer> check(int[][] arr, int M , int N , boolean[][] boolArray) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == 1 && !boolArray[i][j]) {
                    list.add(bfs(i, j,M,N, arr, boolArray));
                }
            }
        }
        return list;
    }

    static int bfs(int x , int y, int M , int N, int[][] arr, boolean[][] boolArray) {
        int count = 0;

        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x,y));
        boolArray[x][y] = true;

        while (!q.isEmpty()) {
            Node n = q.poll();
            for(int i = 0 ; i < 4;i++) {
                int nx = dx[i] + n.x;
                int ny = dy[i] + n.y;
                if (nx < 0 || N <= nx || ny < 0 || M <= ny) continue;
                if (boolArray[nx][ny]) continue;
                if (arr[nx][ny] != 1) continue;

                boolArray[nx][ny] = true;
                q.offer(new Node(nx,ny));
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int tc = sc.nextInt();
        while(tc -- > 0) {
            int M = sc.nextInt();
            int N = sc.nextInt();

            int[][] arr = makeArray(M, N);
            boolean[][] boolArray = makeBoolArray(M, N);
            int K = sc.nextInt();
            while (K-- > 0) {
                int h = sc.nextInt();
                int v = sc.nextInt();
                arr[v][h] = 1;
            }
            System.out.println(check(arr, M, N, boolArray).size());
        }
    }
}

 

사실 쓸모없는 피라미터가 굉장히 많다.

예를들어  bfs란 메소드도 x와 y만 필요하다.

그럼에도 파라미터가 많은 이유는

단순히 값을 넘기기 위한 하나의 방법으로 사용하기 때문이다.

맴버 변수로 빼놓는 방법도 있지만, 이 문제에서는 테스트 케이스도 작성을 해줘야 하기 때문에 일부러 파라미터로 넘기는 방법을 선택했다.

그리고 같은곳을 반복하면 안 되기 때문에 bool배열을 활용해서 같은 곳을 반복하지 않게 처리하였다.

사실 나는 bfs가 더 편하기 때문에 bfs로 풀었지만,

dfs로 푸는 방법도 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

 
 
public class Main {

	
	static int T;
	static int M;
	static int N;
	static int K;
	static int arr[][];
	static boolean check[][];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,1,-1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		int test = 0;
		
		while(test < T) {
			int count = 0;
			String temp[] = br.readLine().split(" ");
			M = Integer.parseInt(temp[0]);
			N = Integer.parseInt(temp[1]);
			K = Integer.parseInt(temp[2]);
			arr = new int[N][M];
			check = new boolean[N][M];
			for(int i = 0; i < K; i++) {
				String str[] = br.readLine().split(" ");
				arr[Integer.parseInt(str[1])][Integer.parseInt(str[0])] = 1;
			}
			
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(arr[i][j] == 1 && check[i][j] == false) {
						dfs(i,j);
						count++;
					}
				}
			}
			System.out.println(count);
			test++;
		}
		
		
		
		
	}
	
	
	static void dfs(int x, int y) {
		check[x][y] = true;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx>=0 && ny >=0 && nx < N && ny < M &&  arr[nx][ny] == 1 && check[nx][ny] == false) {
				dfs(nx,ny);
			}
		}
	}

	

}