[백준] 6186번 Best Grass - Java(BFS)

[백준]  6186번 Best Grass - Java(BFS)

 

문제 출처

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

6186번: Best Grass

 

---

※ 풀이

연속된 잔디밭 뭉텅이(?)의 갯수를 구하는 문제이다.

 

첫 열부터 시작하여 브루트포스 알고리즘으로 싹 구해서 풀면 된다

 

---

※ 소스코드

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

public class Main {

    static boolean[][] visited = new boolean[101][101];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        int row = Integer.parseInt(split[0]);
        int col = Integer.parseInt(split[1]);

        int[][] map = new int[row][col];
        for (int i = 0; i < row; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                char c = line.charAt(j);
                map[i][j] = (c == '#') ? 1 : 0;
            }
        }

        int answer = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    answer++;
                    drawWith(i, j, map);
                }
            }
        }

        System.out.println(answer);
    }

    static void drawWith(int x, int y, int[][] map) {
        if (map[x][y] == 1 && !visited[x][y]) {
            visited[x][y] = true;

            //상
            if (x + 1 < map.length && check(x + 1, y, map)) {
                drawWith(x + 1, y, map);
            }

            //하
            if (x - 1 > 0 && check(x - 1, y, map)) {
                drawWith(x - 1, y, map);
            }

            //좌
            if (y - 1 > 0 && check(x, y - 1, map)) {
                drawWith(x, y - 1, map);
            }

            //우
            if (y + 1 < map[0].length && check(x, y + 1, map)) {
                drawWith(x, y + 1, map);
            }
        }
    }

    static boolean check(int x, int y, int[][] map) {
        return map[x][y] == 1;
    }
}