#1012 : 유기농 배추

풀이방법

사용된 것:

깊이우선탐색(DFS)

 

2022.05.28

방문한 적 없는 배추가 발견될 때마다

필요한 지렁이 수를 1 증가시키고,

그 배추를 시작으로 인접한 배추들을 모두 방문해주면 된다.

 

다시 말하자면

정답을 저장할 int형 변수 answer을 선언한 뒤 0으로 초기화한다.

그 후 밭의 모든 칸에 대하여,

(이번 칸이 배추임) AND (이번 칸을 방문한 적 없음) 이 true일 경우

answer을 1 증가시키고, 이번 칸에 대하여 dfs를 돌아준다.

 

코드

Java(2022.05.28)

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

public class Main {
	
	static boolean[][] map;	//배추밭
	static boolean[][] visited;	//방문여부 저장용 배열
	static int answer;	//정답(필요한 지렁이의 수)
	static int n, m;	//밭의 세로길이, 가로길이
	//아래는 상하좌우 재귀 시 좌표변경용 배열
	static int[] r = {-1, 1, 0, 0};
	static int[] c = {0, 0, -1, 1};
	
	static void dfs(int row, int col) {
		if(row==-1 || col==-1 || row>=n || col>=m) return;	//밭 바깥이면 return
		if(visited[row][col]) return;	//이미 방문한 곳이면 return
		if(!map[row][col]) return;	//배추가 없는 곳이면 return
		//방문했다고 표시
		visited[row][col] = true;
		//상하좌우에 대하여 재귀
		for(int i = 0; i<4; i++) dfs(row+r[i], col+c[i]);
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int testCase = Integer.parseInt(br.readLine());		
		
		for(int t= 0; t<testCase; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			map = new boolean[n][m];
			visited = new boolean[n][m];
			answer = 0;
			//배추 위치 읽어오기
			for(int i = 0; i<k; i++) {
				st = new StringTokenizer(br.readLine());
				int col = Integer.parseInt(st.nextToken());
				int row = Integer.parseInt(st.nextToken());
				map[row][col] = true;
			}
			//아직 방문하지 않은 배추에 대하여 카운트하고 재귀
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<m; j++) {
					if(map[i][j] && !visited[i][j]) {
						answer++;
						dfs(i, j);
					}
				}
			}
			//정답문자열에 정답 값 추가
			sb.append(answer + System.lineSeparator());
		}
		
		//정답 출력
		System.out.print(sb);
	}

}