[백준/JAVA] 1012번: 유기농 배추

🔺 문제

1012번: 유기농 배추

 

 

🔺 코드

1) DFS 풀이

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int[][] map;
    static boolean[][] visited;
    static int T, M, N, K;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        T = Integer.parseInt(br.readLine());
        
        while(T -- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            M = Integer.parseInt(st.nextToken());   // 가로
            N = Integer.parseInt(st.nextToken());   // 세로
            K = Integer.parseInt(st.nextToken());   // 위치
            
            map = new int[M][N];
            visited = new boolean[M][N];
            int cnt = 0;
            
            while(K -- > 0) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                
                map[a][b] = 1;
            }
            
            for(int i = 0 ; i< M ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    if(!visited[i][j] && map[i][j] == 1) {
                        dfs(i, j);
                        cnt++;
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
 
        System.out.println(sb);
    }
    
    private static void dfs(int a, int b) {
        if(visited[a][b]) return;
        
        visited[a][b] = true;
        for(int d = 0 ; d < 4 ; d++) {
            int x = dx[d] + a;
            int y = dy[d] + b;
            
            if(x < 0 || x >= M || y < 0 || y >= N)    continue;
            if(!visited[x][y] && map[x][y] == 1) {
                dfs(x, y);
            }
        }
    }
}
 

 

 

 

2) BFS 풀이

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int[][] map;
    static boolean[][] visited;
    static int T, M, N, K;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        T = Integer.parseInt(br.readLine());
        while(T -- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            M = Integer.parseInt(st.nextToken());   // 가로
            N = Integer.parseInt(st.nextToken());   // 세로
            K = Integer.parseInt(st.nextToken());   // 위치
            
            map = new int[M][N];
            visited = new boolean[M][N];
            int cnt = 0;
            
            while(K -- > 0) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                
                map[a][b] = 1;
            }
            
            for(int i = 0 ; i< M ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    if(!visited[i][j] && map[i][j] == 1) {
                        bfs(i, j);
                        cnt++;
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        
        System.out.println(sb);
    }
    
    private static void bfs(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b});
        
        visited[a][b] = true;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = dx[d] + now[0];
                int y = dy[d] + now[1];
                
                if(x < 0 || x >= M || y < 0 || y >= N)    continue;
                if(!visited[x][y] && map[x][y] == 1) {
                    queue.add(new int[] {x, y});
                    visited[x][y] = true;
                }
            }            
        }
    }
}
 

 

✅ 해결 아이디어
✔ DFS / BFS
- 각 점에 대해 dfs/bfs 수행하면서 dfs/bfs 수행 횟수 계산 (= 덩어리 수)

---

🔺 다른 풀이들

- 대체로 비슷함

 

---

💬 느낀 점

재밌는 bfs dfs...

 

 

1회독	2회독	3회독	4회독	5회독
V