[백준] 1012 : 유기농 배추 (JAVA/자바)

문제

BOJ 1012 : 유기농 배추 - https://www.acmicpc.net/problem/1012

풀이

유기농 배추가 모여있는 묶음(?)의 개수를 카운트하면 된다. 이중 for문으로 각 위치를 보며 1인 경우(배추가 있는 경우) BFS로 주변에 붙어있는 배추가 있는지 확인한다. 탐색된 배추들의 값은 -1로 바꿔주어(visited 역할) 다시 for문으로 배추가 있는지 확인할 때 제외되도록 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static class Loc{
        int i;
        int j;

        public Loc(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tk = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while(tk-- > 0) {
            String[] inputs = br.readLine().split(" ");
            int m = Integer.parseInt(inputs[0]);
            int n = Integer.parseInt(inputs[1]);
            int k = Integer.parseInt(inputs[2]);

            map = new int[n][m];

            for (int i = 0; i < k; i++) {
                inputs = br.readLine().split(" ");
                int x = Integer.parseInt(inputs[0]);
                int y = Integer.parseInt(inputs[1]);
                map[y][x] = 1;
            }

            int cnt = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if(map[i][j] == 1){
                        bfs(i, j, n, m);
                        cnt++;
                    }
                }
            }

            sb.append(cnt+"\n");

        }
        System.out.println(sb);
    }

    public static void bfs(int i, int j, int n, int m) {
        Queue<Loc> q = new LinkedList<>();
        q.add(new Loc(i, j));
        map[i][j] = -1; // visited

        int[] mi = {0, 0, -1, 1};
        int[] mj = {1, -1, 0, 0};

        while (!q.isEmpty()) {
            Loc now = q.poll();

            for (int d = 0; d < 4; d++) {
                int ni = now.i + mi[d];
                int nj = now.j + mj[d];

                if(ni<0 || nj<0 || ni>=n || nj>=m) continue;

                if(map[ni][nj]==1){
                    map[ni][nj]=-1;
                    q.add(new Loc(ni, nj));
                }
            }
        }
    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
✔ 난이도 - ⚪ Silver 2

참고 사이트

딱히 없음