[백준 1012] 유기농 배추 (DFS, BFS)

[백준 1012] 유기농 배추 (DFS, BFS)

문제 출처 : 링크

DFS와 BFS를 활용해서 모두 풀 수 있는 문제다. 

1로 표시된 구간마다 묶어서 총 몇 개가 있는지 구해야 한다.

예전에 처음 공부하면서 풀었던 백준 2667번 단지번호 문제(링크)와 유사하다.

DFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class 백준1012_dfs {
    
    static int M, N, K; // M : 행, N : 열, K : 배추개수
    static int[][] map; // map[N][M]
    static boolean[][] visited;
    
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    static int count;
 
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int ts = Integer.parseInt(br.readLine());
        
        for (int t = 1; t <= ts; t++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            M = Integer.parseInt(st.nextToken()); // 행
            N = Integer.parseInt(st.nextToken()); // 열
            
            map = new int[N][M];
            visited = new boolean[N][M];
            count = 0;
            
            K = Integer.parseInt(st.nextToken()); // 배추 개수
            
            for (int i = 0; i < K; i++) {
                
                st = new StringTokenizer(br.readLine(), " ");
                
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                map[y][x] = 1;
            }
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    
                    if(map[i][j] == 1 && !visited[i][j]){ // 배추가 있고, 방문하지 않았을 때
                        dfs(i,j); 
                        count++; // 한 구간 끝나면 count 추가
                    }
                    
                }
            }
            
            System.out.println(count);
            
        }
    }
    
    static void dfs(int y, int x){
        
        if(visited[y][x]) return;
        
        visited[y][x] = true;
        
        for (int i = 0; i < 4; i++) {
            
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(map[ny][nx] == 1 && !visited[ny][nx]){
                dfs(ny, nx);
            }
        }
        
        
    }
 
}
 

BFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Point {
    int y;
    int x;
    
    Point(int y, int x){
        this.y = y;
        this.x = x;
    }
}
 
public class 백준1012_bfs {
    
    static int M, N, K; // M : 행, N : 열, K : 배추개수
    static int[][] map; // map[N][M]
    static boolean[][] visited;
    
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    static int count;
 
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int ts = Integer.parseInt(br.readLine());
        
        for (int t = 1; t <= ts; t++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            M = Integer.parseInt(st.nextToken()); // 행
            N = Integer.parseInt(st.nextToken()); // 열
            
            map = new int[N][M];
            visited = new boolean[N][M];
            count = 0;
            
            K = Integer.parseInt(st.nextToken()); // 배추 개수
            
            for (int i = 0; i < K; i++) {
                
                st = new StringTokenizer(br.readLine(), " ");
                
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                map[y][x] = 1;
            }
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    
                    if(map[i][j] == 1 && !visited[i][j]){ // 배추가 있고, 방문하지 않았을 때
                        bfs(i,j); 
                        count++; // 한 구간 끝나면 count 추가
                    }
                    
                }
            }
            
            System.out.println(count);
            
        }
    }
    
    static void bfs(int y, int x){
        
        Queue<Point> q = new LinkedList<Point>();
        
        Point p1 = new Point(y, x);        
        q.add(p1);
        
        while(!q.isEmpty()){
            
            Point p2 = q.poll();
            visited[p2.y][p2.x] = true;
            
            for (int i = 0; i < 4; i++) {
                int ny = p2.y + dy[i];
                int nx = p2.x + dx[i];
                
                if(ny >= 0 && nx >= 0 && ny < N && nx < M){
                    
                    if(map[ny][nx] == 1 && !visited[ny][nx]){
                        Point p3 = new Point(ny,nx);
                        q.add(p3);
                        visited[p3.y][p3.x] = true;
                    }
                }
            }
            
            
        }
        
    }
    
 
}