[Baekjoon] #1012 유기농 배추

[Baekjoon] [https://www.acmicpc.net/problem/1012]

기본적인 그래프 문제

풀이 )

1. 이중 포문에서 배추의 위치를 찾는다. 또한 현재 방문하지 않은 배추의 위치여야한다.

2. 찾은 배추의 위치에서 인접한 배추의 위치를 계속 찾는다. 또한 방문하지 않은 인접 위치여야한다. ( ←↑→↓ : 순서 xx = [-1,0,1,0] yy = [0,-1,0,1] ) // 이를 재귀탐색 DFS

3. 배추가 인접하지 않거나 이미 방문한 지역이면 getDFS 함수를 빠져나온다.

4. 이중포문으로 돌아와서 다시 배추의 위치를 찾는다

5. 1~4 반복.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int m; //가로
	static int n; //세로
	static int k; //배추의 개수
	static int[][] land;
	static int[][] visit;
	static int[] xx = {-1, 0, 1, 0};
	static int[] yy = {0, -1, 0, 1};


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> answer = new ArrayList<>();
		int tc = sc.nextInt();

		while(tc>0){
			m = sc.nextInt();
			n = sc.nextInt();
			k = sc.nextInt();

			land = new int[m][n];
			visit = new int[m][n];
			int worms = 0;

			for(int i=0;i<k;i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				//배추의 좌표 x,y
				land[x][y] = 1;
			}

			for(int i=0;i<m;i++){
				for(int j=0;j<n;j++){
					if(land[i][j] == 1 && visit[i][j] == 0){
						getDFS(i, j);
						worms++;
					}
				}
			}

			answer.add(worms);
			tc--;
		}

		

		for(int i=0;i<answer.size();i++){
			System.out.println(answer.get(i));
		}
	}

	public static void getDFS(int x, int y){
		visit[x][y] = 1;

		for(int i=0;i<4;i++){
			int ax = x+xx[i];
			int ay = y+yy[i];

			if(ax>=0 && ax<m && ay>=0 && ay<n){
				if(land[ax][ay] == 1 && visit[ax][ay] == 0){
					getDFS(ax, ay);
				}
			}
		}
	}
}