[Baekjoon] 백준 11123번: 양 한마리... 양 두마리... (JAVA)

문제 11123

11123번: 양 한마리... 양 두마리...

[ 풀이 과정 ]

양들의 무리만 카운트하면 되므로 map[][]에 양과 풀을 저장한 후 for()문으로 순회하면서 '#' 가 있는 위치에서 카운트를 하나 증가시키고, bfs()를 돌려주면 상하좌우로 붙어있는 '#' 끼리 최대한 방문하게 됩니다. 
(행, 열의 최대 크기가 각각 100이므로 시간복잡도는 충분합니다.)

!! for()문으로 순회할 때 방문체크까지 해주어야 정점을 중복해서 방문하지 않게 됩니다.

[ 코드 ]

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

public class Main {
    private static int H, W;
    private static char[][] map;
    private static boolean[][] visit;
    private static int[] moveR = {-1, 1, 0, 0};
    private static int[] moveC = {0, 0, -1, 1};

    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 test = 0; test < T; test++) {
            st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            map = new char[H][W];
            visit = new boolean[H][W];

            String str;
            for (int i = 0; i < H; i++) {
                str = br.readLine();
                for (int j = 0; j < W; j++) {
                    map[i][j] = str.charAt(j);
                }
            }

            int cnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == '#' && !visit[i][j]) {
                        cnt++;
                        bfs(i, j);
                    }
                }
            }
            bw.write(String.valueOf(cnt));
            bw.newLine();
        }
        bw.flush();
    }

    private static void bfs(int r, int c) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(r, c));
        visit[r][c] = true;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextR = cur.r + moveR[i];
                int nextC = cur.c + moveC[i];
                if (nextR < 0 || nextR >= H || nextC < 0 || nextC >= W) continue;
                if (visit[nextR][nextC]) continue;
                if (map[nextR][nextC] == '#') {
                    queue.offer(new Node(nextR, nextC));
                    visit[nextR][nextC] = true;
                }
            }
        }
    }

    private static class Node {
        int r, c;
        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}