[백준] 1012 유기농 배추 - BFS(너비우선탐색) JAVA

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

코드설명

BFS(너비우선탐색) 를 활용합니다.

 

만약 배추가 심어져있는 부분을 만난다면 BFS를 실행하고, GlobalVisited 배열을 활용하여 이미 배추그룹이 만들어진 곳은 더이상 방문하지않고, 처음으로 배추그룹을 만들 수 있는 곳만 방문하면 됩니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    private static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
     
        int T = Integer.parseInt(st.nextToken());
        while(T-- > 0) {
        	answer = 0;
        	st = new StringTokenizer(br.readLine());
        	M = Integer.parseInt(st.nextToken());
        	N = Integer.parseInt(st.nextToken());
        	K = Integer.parseInt(st.nextToken());
        	
        	arr = new int[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;
        	}
        	
        	int[][] visited = new int[M][N];
        	for(int i=0;i<M;i++) {
        		Arrays.fill(visited[i], -1);
        	}
        	for(int i=0;i<M; i++) {
        		for(int j=0;j<N; j++) {
        			if(arr[i][j] == 1 && visited[i][j] == -1) {
        				BFS(i, j, visited);
        			}
        		}
        	}
        	
        	System.out.println(answer);
        }
        
    }
    
    public static void BFS(int r, int c, int[][] visited){
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0, 0,-1,1};
    	Queue<Node> q = new LinkedList<Node>();
    	q.offer(new Node(r, c));
    	visited[r][c] = 1;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		
    		for(int dir = 0; dir < 4; dir++) {
    			int nr = temp.r + dx[dir];
    			int nc = temp.c + dy[dir];
    			
    			if(nr < 0 || nr >=M || nc < 0 || nc >= N) continue;
    			if(visited[nr][nc] == 1) continue;
    			if(arr[nr][nc] == 0) continue;
    			q.offer(new Node(nr, nc));
    			visited[nr][nc] = 1;
    		}
    	}
    	answer += 1;
    }
    
    private static class Node{
    	int r;
    	int c;
    	public Node(int r, int c) {
    		this.r=r;
    		this.c=c;
    	}
    }
}