백준 1012 - 유기농 배추 (자바 - 그래프)

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

1012번: 유기농 배추

 

* 문제 요약

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추 흰지렁이를 구입하기로 결심한다.

이 지렁이는 배추 근처에 서식하며 해충을 잡아 먹음으로서 배추를 보호한다. 특히, 어떤 배추에 흰 지렁이가 한 마리라도 살고 있으면, 이 지렁이는 인접한 다른 배추로 이동할 수 있어 그 배추들 역시 해충으로부터 보호받을 수 있다.

한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

 

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

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

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

 

* 입력

입력의 첫 줄에는 테스트 케이스의 갯수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로 길이 M (1 <= M <= 50) 과 세로 길이 N (1 <= N <= 50), 그리고 배추가 심어져 있는 위치의 갯수 K (1 <= K <= 2,500) 이 주어진다. 그 다음 K줄에는 배추의 위치 X (0 <= X <= M - 1), Y (0 <= Y <= N - 1) 가 주어진다. 

두 배추의 위치가 같은 경우는 없다.

 

* 출력

각 테스트 케이스에 대해 필요한 최소의 배추 흰 지렁이 마리 수를 출력한다.

 

* 예시

 

* 해결 과정

2차원 배열에서 상,하,좌,우로 인접한 노드들끼리만 연결되어서 만들어진 그래프가 있을 때 그래프들의 갯수를 구해주는 문제이다.

입력으로 들어온 배추의 갯수 K만큼 반복을 수행하며 2차원 배열 상에서 입력으로 들어온 인덱스 (i, j) 값을 1로 초기화하여 배추의 위치를 기록해준다.

이때 주의해야할 점은 인덱스 i j 가 입력으로 들어올 때 입력 조건을 보면 처음에 오는 값의 범위가 (0 <= X <= M - 1), 두번째로 오는 값의 범위가 (0 <= Y <= N - 1) 인 것을 보았을 때 첫번째로 오는 값이 열에 대한 정보, 두번째로 오는 값이 행에 대한 정보라는 뜻이므로 2차원 배열에서 입력받은 인덱스의 값을 1로 초기화할 때 maps[j][i] = 1 과 같이 해주어야 한다.

 

2차원 배열 상에서 배추의 위치에 대한 기록이 끝나고 나면 이중 반복문을 통해 2차원 배열의 각 인덱스를 탐색하되, 현재 탐색중인 인덱스의 값이 1이고, visited 배열 상에서 현재 인덱스의 값이 false 인 경우 그래프의 갯수를 나타내는 변수 값을 1 증가시켜주고 dfs(int a, int b) 메소드를 수행해준다.

 

dfs 메소드 내부에서는 우선 visited 배열에서 매개변수로 전달받은 인덱스 (a, b) 에 해당하는 값을 true 로 바꿔주고, 현재 그래프에서 각 노드들이 상,하,좌,우 4방향으로만 인접해서 이루어져 있는 것을 표현하기 위해 만든 배열 dx, dy 를 이용해 현재 인덱스를 기준으로 각 방향에 대한 탐색을 수행한다.

만약 반복문 도중 현재 방향의 값이 2차원 배열의 범위를 벗어나지 않으면서 그 값이 1이고, visited 배열 상에서 현재 방향의 값이 false 인 경우 dfs(int aa, int bb) 메소드를 재귀호출 해준다.

 

재귀호출이 끝났다면 2차원 배열에서 현재 발견된 1 값을 기준으로 연결 되어있는 그래프의 탐색이 모두 끝났다는 뜻이므로 이중 반복문으로 돌아가서 그래프의 갯수를 나타내는 변수 값을 1 증가시켜주고 다음 인덱스에 대한 탐색으로 넘어간다.

반복문이 끝나면 2차원 배열에서 찾은 그래프의 갯수를 출력시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

//유기농 배추
public class Main {

	static int m; // 가로길이(1~50)
	static int n; // 세로길이(1~50)
	static int k; // 배추가 심어져있는 위치의 갯수(1~2500)
	static int[][] maps; // 배추 지도
	static boolean[][] visited;

	static int[] dx = { -1, 1, 0, 0 }; // 가로
	static int[] dy = { 0, 0, -1, 1 }; // 세로

	public static void main(String[] args) throws IOException {
		new Main().solution();
	}

	private void solution() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] input = br.readLine().split(" ");
		int t = Integer.parseInt(input[0]);

		for (int i = 0; i < t; i++) {
			input = br.readLine().split(" ");
			m = Integer.parseInt(input[0]);
			n = Integer.parseInt(input[1]);
			k = Integer.parseInt(input[2]);

			maps = new int[n][m];
			visited = new boolean[n][m];
			int count = 0;

			// 배추 심어져있는 갯수
			int x; // 가로
			int y; // 세로
			for (int j = 0; j < k; j++) {
				input = br.readLine().split(" ");
				x = Integer.parseInt(input[0]);
				y = Integer.parseInt(input[1]);
				// 지도에 넣어주기
				maps[y][x] = 1;
			}

			// 지렁이 둘 구간 탐색
			for (int a = 0; a < n; a++) {
				for (int b = 0; b < m; b++) {
					if (maps[a][b] == 1 && !visited[a][b]) {
						dfs(a, b);
						count++;
					}
				}
			}
			// 결과값 출력
			bw.write(count + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	static void dfs(int a, int b) {
		visited[a][b] = true;

		for (int i = 0; i < 4; i++) {
			int aa = a + dx[i];
			int bb = b + dy[i];

			if (aa < 0 || aa >= n || bb < 0 || bb >= m) {
				continue;
			} else if (maps[aa][bb] == 1 && !visited[aa][bb]) {
				dfs(aa, bb);
			}
		}
	}
}

 

2차원 배열상에서 DFS 알고리즘을 통해 상,하,좌,우로 인접해 있는 노드들로만 연결되어 있는 그래프의 갯수를 구해주면 되므로 그래프 탐색 문제에 해당한다.