[자바] 백준 1012번 유기농 배추

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

 

dfs나 bfs를 사용하여 푸는 문제로 위, 아래, 왼, 오 네 가지 방향으로 가보면서 만약 인접한 노드가 있으면 방문하면서 최소한으로 배추흰지렁이를 구입하도록 하는 문제였다. 아직 생으로 dfs, bfs 문제를 푸는 게 좀 어려워서 다른 사람의 코드를 참고하여 dfs와 bfs 모두를 사용하여 풀어보았다. 사실 어떤 식으로 푸는지 감은 오는데 막상 혼자 풀어보려고 하면 잘 안풀린다. 동일한 문제를 반복적으로 풀어보면서 내가 어떤 부분이 약한지 파악하는 것도 필요할 것 같다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0}; // 위, 아래, 왼, 오
    static int[][] map;
    static boolean[][] visit;
    static int n, m, k, count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < t; i++){
            count = 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];
            visit = new boolean[m][n];

            for(int j = 0; j < k; j++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                map[a][b] = 1;
            }

            for(int j = 0; j < m; j++){
                for(int l = 0; l < n; l++){
                    if(map[j][l] == 1 && !visit[j][l]){
//                        dfs(j, l);
                        bfs(j, l);
                        count++; // 조건에 맞아서 내부로 들어오면 count를 증가하고 해당하는 값과 인접한 곳에 대해서는 dfs 함수를 통해 visit 배열에 값을 넣는다.
                    }
                }
            }
            bw.write(String.valueOf(count));
            bw.newLine();
            bw.flush();
        }
        bw.close();
    }

    public static void dfs(int a, int b){
        visit[a][b] = true;
        for(int i = 0; i < 4; i++){
            int next_a = a + dx[i];
            int next_b = b + dy[i];
            if(next_b < n && next_a < m && next_b >= 0 && next_a >= 0){
                if(map[next_a][next_b] == 1 && !visit[next_a][next_b]){
                    dfs(next_a, next_b);
                }
            }
        }
    }

    public static void bfs(int a, int b){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b});

        while(!queue.isEmpty()){
            a = queue.peek()[0];
            b = queue.peek()[1];

            visit[a][b] = true;
            queue.poll(); // [0]과 [1] 모두 없앰
            for(int i = 0; i < 4; i++){
                int next_a = a + dx[i];
                int next_b = b + dy[i];

                if(next_b >= 0 && next_a >= 0 && next_a < m && next_b < n){
                    if(map[next_a][next_b] == 1 && !visit[next_a][next_b]){
                        queue.add(new int[]{next_a, next_b});
                        visit[next_a][next_b] = true;
                    }
                }
            }
        }
    }
}