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

▶ 문제

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

1012번: 유기농 배추

 

▶ 설명

단지번호 붙이기 문제와 아주 유사하다. 

입력받는 방식이 다르고, 1끼리 인접해있는 곳의 개수를 구해주기만 하면 되겠다.

 

먼저, 배추가 있는 곳을 1, 없는 곳을 0으로 표시할 배추밭 2차원 배열을 구성한다.

2차원 배열을 초기화할 때 값이 모두 0이므로 이제 1인 곳만 알아내서 값을 주도록 하면 된다.

입력에서 1인 곳의 인덱스를 주고 있으므로 편하게 1을 배열에 저장할 수가 있다.

 

그렇게 배추밭이 만들어졌으면 1인 곳을 DFS, BFS로 탐색을 진행시킨다. 

이 문제에서 나는 DFS를 활용하였다.

 

DFS 함수를 호출할 때마다 인접한 곳이 1일 경우 0으로 값을 변경하여 다음에 방문에서 제외되도록 하고, 

더이상 방문할 인접한 1이 없을 경우 DFS 함수에서 빠져나와 카운트를 센다.

 

 

 

▶ 문제 풀이

🌱 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int m, n;
	static int[][] graph;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());

			graph = new int[m][n];

			while (k-- > 0) {
				st = new StringTokenizer(br.readLine(), " ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());

				graph[x][y] = 1;
			}


			int result = 0;

			for (int i = 0; i < graph.length; i++) {
				for (int j = 0; j < graph[i].length; j++) {
					if (dfs(i, j)) {
						result++;
					}
				}
			}

			sb.append(result).append("\n");
		}
		System.out.println(sb);

	}

	private static boolean dfs(int i, int j) {

		if (i >= m || j >= n || i < 0 || j < 0) {
			return false;
		}

		if (graph[i][j] == 1) {

			graph[i][j] = 0;

			dfs(i - 1, j);
			dfs(i, j - 1);
			dfs(i, j + 1);
			dfs(i + 1, j);
			return true;
		}

		return false;
	}
}

 

 

 

 

 

 

▶ Log

dfs 함수(메소드)를 만들 때 반환타입을 boolean으로 할지, int으로 할지, 아니면 void 로 할지를 문제 유형에 따라 알맞게 사용하는 것이 관건인 듯 하다.