[백준 1012번] 유기농 배추

문제 링크: 1012번 제목

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

 

연결된 노드의 집합의 개수를 구하는 문제이다. 앞선 문제처럼, visited를 선언하지 않고도 0, 1, 2로 구분하는 방식으로 해서 문제를 풀어갈 수도 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] drow = {0, 0, 1, -1};
    static int[] dcol = {1, -1, 0, 0};

    static class Pos {
        int row;
        int col;

        Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static void bfs(int i, int j, int[][] map, boolean[][] visited, int m, int n) {
        Queue<Pos> queue = new LinkedList<>();
        queue.offer(new Pos(i, j));

        while (!queue.isEmpty()) {
            Pos cur = queue.poll();
            int row = cur.row;
            int col = cur.col;

            for (int d = 0; d < 4; d++) {
                int nrow = row + drow[d];
                int ncol = col + dcol[d];

                if (nrow<0 || ncol<0 || nrow>=n || ncol>=m || visited[nrow][ncol] || map[nrow][ncol]!=1)
                    continue;

                visited[nrow][ncol] = true;
                queue.offer(new Pos(nrow, ncol));
            }
        }
    }

    static void solution(int m, int n, int[][] map) {
        boolean[][] visited = new boolean[n][m];

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

        System.out.println(cnt);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcs = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

        for (int tc = 0; tc < tcs; tc++) {
            int[] temp1 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int m = temp1[0];
            int n = temp1[1];
            int k = temp1[2];

            int[][] map = new int[n][m];
            for (int i = 0; i < k; i++) {
                int[] temp2 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                map[temp2[1]][temp2[0]] = 1;
            }

            solution(m, n, map);
        }

        br.close();
    }
}