[백준] 11123번

끝까지 전부 순회하면서 양이 몇 무리 있는지를 세야하는 문제라 DFS로 풀었다.

 

다른 문제들과는 달리 map이 숫자로 이루어진 게 아니라, 문자로 이루어져있기 때문에 boolean 으로 2차원 배열을 만들어줬다. dfs를 돌면서 상하좌우를 살필 때, 경계 조건을 잘 설정하지 않으면 ArrayIndexOutOfBoundsException이 발생하니 주의해야 한다.

 

처음에는 BFS, DFS를 이해하는 게 정말 어려웠는데, 기초 문제부터 하나씩 풀다보니까 슬슬 감이 잡히는 것 같다.

BFS, DFS.. 좋아지기.. 시작..

 

 

 

public class Main {

    static boolean[][] map;
    static boolean[][] check;
    static StringBuilder sb = new StringBuilder();
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};
    static int x, y;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int H = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            map = new boolean[H][W];
            check = new boolean[H][W];
            int count = 0;

            for (int i = 0; i < H; i++) {
                String line = br.readLine();
                for (int j = 0; j < W; j++) {
                    if (line.charAt(j) == '#')
                        map[i][j] = true;
                }
            }
            br.close();

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] && !check[i][j]) {
                        dfs(i, j);
                        count++;
                    }
                }
            }

            sb.append(count).append('\n');
        }

        System.out.println(sb.toString());
    }

    private static void dfs(int height, int width) {
        check[height][width] = true;

        for (int i = 0; i < 4; i++) {
            x = width + dx[i];
            y = height + dy[i];

            if (x >= 0 && y >= 0 && x < map[0].length && y < map.length) {
                if (map[y][x] && !check[y][x])
                    dfs(y, x);
            }
        }
    }
}