[백준 1012] - [dfs] - 유기농 배추 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/1012

---

이 문제는 DFS 간단하게 풀 수 있는 문제이다.

다만 주의해야 할 부분이 있는데 제한시간은 1초인데 여러개의 테스트 케이스가 주어지니 제한시간내에 모든 테스트 게이스를 

풀기 위해선 불필요한 좌표까지 dfs로 접근할 필요가 없다.

• 배추의 좌표를 정수형 배열 타입의 큐에 저장한다.
  
  
• 모든 입력이 완료되고 queue가 빌때까지 queue에서 하나씩 추출해가면서 dfs를 돌린다.
  
• queue에 있는 좌표는 부조건 배추가 심어저 있는 좌표이다.
  
• 추출된 좌표가 이전에 방문한 이력이 없는 경우만 dfs 탐색을 한다.

위에 나열한 순서와 조건으로 DFS 탐색을 시도하면 문제는 아주 쉽게 풀린다.

모든 좌표에 방문여부와 배추가 심어진 좌표인지 확인면서 DFS 탐색을 한다면 시간초과를 받을것이다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    
    public static Queue<int[]> queue;
    public static int[][] arr;
    public static boolean[][] visited;
    
    public static int ROW;
    public static int COL;
    public static int result;
    
    public static int[] dy = {-1, 1, 0, 0}; // 상하좌우
    public static int[] dx = {0, 0, -1, 1}; // 상하좌우
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        StringBuilder sb = new StringBuilder();
        
        int testCase = Integer.parseInt(br.readLine());
        
        while(testCase-- > 0) {
            st = new StringTokenizer(br.readLine());
            
            COL = Integer.parseInt(st.nextToken());
            ROW = Integer.parseInt(st.nextToken());
            
            int lineCnt = Integer.parseInt(st.nextToken());
            
            // 값 초기화
            queue = new LinkedList<>();
            arr = new int[ROW][COL];
            visited = new boolean[ROW][COL];
            result = 0;
            
            while(lineCnt-- > 0) {
                st = new StringTokenizer(br.readLine());
                
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                arr[y][x] = 1;
                
                queue.offer(new int[] {y, x});
            }
            
            while(!queue.isEmpty()) {
                int y = queue.peek()[0];
                int x = queue.peek()[1];
                queue.poll();
                
                if(!visited[y][x]) {
                    dfs(y, x);
                    result++;
                }
            }
            
            sb.append(result +"\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public static void dfs(int y, int x) {
        visited[y][x] = true;
        
        for(int i=0; i <4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            
            if(yy < 0 || xx < 0 || yy >= ROW || xx >= COL) continue;
            
            if(arr[yy][xx] == 1 && !visited[yy][xx]) dfs(yy, xx);
        }
    }
}