백준 1012 - 유기농배추 DFS (JAVA)

백준 1012 - 유기농배추 DFS (JAVA)

 

 

DFS의 정석과도 같은 문제네요.

 

www.acmicpc.net/problem/1000

1000번: A+B

visits처리를 잘못해서 좀 헤매다가 풀었습니다.

DFS visits 처리는 DFS들어가면서 바로 해주는게 좋은것 같네요. 

 

import java.util.*;
 
public class Yuginong {
    
    static int t,n,m,k,result;
    static int map [][];
    static boolean visits[][];
    static int dx[] = {1, -1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        t = sc.nextInt();
        
        for (int test_case=1; test_case<=t; test_case++) {
            
            m = sc.nextInt();
            n = sc.nextInt();
            k = sc.nextInt();
            
            map = new int[n+2][m+2];
            visits = new boolean[n+2][m+2];
            result = 0;
            
            for(int i=1; i<=k; i++) {
                int temp1 = sc.nextInt()+1;
                int temp2 = sc.nextInt()+1;                
                map[temp2][temp1] = 1;
            }
            
            
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++) {
                    if(visits[i][j]==false && map[i][j] ==1) {
                        visits[i][j] =true;
                        dfs(i, j);
                        result++;
                    }
                }
            }
            System.out.println(result);
        }
    }
    
    private static void dfs(int x, int y) {
        visits[x][y] = true; // 방문체크
        for(int i=0; i<4; i++) {
            int new_x = x + dx[i]; // 1 -1 0 0
            int new_y = y + dy[i]; // 0 0 1 -1
            
            if (new_x<=n || new_y<=m || new_x>=0 || new_y>=0) {
                if(visits[new_x][new_y]==false && map[new_x][new_y]==1) {
                    dfs(new_x,new_y);
                }
            }    
        }
    }
}