백준 1012 유기농배추(DFS,BFS) / JAVA

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

1012번: 유기농 배추

 

1. DFS & BFS 함수

 * DFS

public static void dfs(int x, int y) {
    visited[x][y] = true;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < M && ny >= 0 && ny < N) {
            if(arr[nx][ny] == 1 && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }
}

* BFS

public static void bfs(int x, int y) {
    Queue<Point> queue = new LinkedList<>();
    queue.offer(new Point(x,y));
    visited[x][y] = true;

    while(!queue.isEmpty()) {
        Point point = queue.poll();
        for(int i = 0; i < 4; i++) {
            int nx = point.x + dx[i];
            int ny = point.y + dy[i];
            if(nx >= 0 && nx < M && ny >= 0 && ny < N) {
                if(arr[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.offer(new Point(nx,ny));
                }
            }
        }
    }
}

2. 메인함수

public class boj_1012 {

	static int M, N;
	static int[][] arr;
	static boolean[][] visited;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	} // bfs일때만필요
    
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int[] result = new int[T];
		for(int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			arr = new int[M][N];
			visited = new boolean[M][N];
			
			// 배추밭그리기
			for(int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				arr[x][y] = 1; 
			}
			
			for(int j = 0; j < M; j++) {
				for(int k = 0; k < N; k++) {
					if(arr[j][k] == 1 && !visited[j][k]) {
						result[t]++;
						dfs(j,k) or bfs(j,k);
					}
					
				}
			}
		}
		
		for(int x : result) {
			System.out.println(x);
		}
	}
 }