백준 온라인 저지 - 1012번: 유기농 배추

🔍  문제

---

 

1012번: 유기농 배추

 

✏️  풀이 - Java

---

 

너무 bfs로만 문제를 푼 것 같아서 이번에는 재귀를 이용해서 dfs로 풀어보았다. 입력값으로 테스트케이스가 1개 이상으로 들어오기 때문에 테스트케이스 개수 t값을 받아준 후 t값 만큼 배추벌레 세기를 반복하였다. 인접한 배추들은 재귀를 통해 탐색시 visit[][]값을 true로 바꿔주고, 새로운 탐색을 들어갈때 마다 cnt++를 해주었다. Codility가 사이트가 깔끔하긴 한데 다른 사람 코드를 볼 수 있는 점이나 문제가 다양하다는 점에서는 boj가 더 좋은 것 같다. 다만 문제 제출 후 내 코드에 대한 분석은 Codility가 더 낫다. 두 사이트 모두 장단점이 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st;

    int t;
    int m;
    int n;
    int k;
    int[][] map;
    boolean[][] visit;
    ArrayList<Integer> wormCnt = new ArrayList<>(); 

    void init() throws IOException {
        t = Integer.parseInt(br.readLine());

        for(int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());

            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            map = new int[n][m];
            visit = new boolean[n][m];

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

            solve();
        }

    }

    private void solve() {
        int cnt = 0; //벌레 수

        for(int j = 0; j < n; j++) {
            for(int h = 0; h < m; h++) {
                if(map[j][h] == 1 && !visit[j][h]) {
                    dfs(j, h);
                    cnt++;
                }
            }
        }

        wormCnt.add(cnt);
    }

    private void dfs(int j, int h) {
        if(j < 0 || j >= n || h < 0 || h >= m) return;
        if(visit[j][h]) return;
        if(map[j][h] == 1 && !visit[j][h]) {
            visit[j][h] = true;
            dfs(j-1, h);
            dfs(j+1, h);
            dfs(j, h-1);
            dfs(j, h+1);
        }
    }

    private void print() throws IOException {
        br.close();

        for(int cnt: wormCnt) {
            bw.write(cnt + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.init();
        main.print();
    }
}