[백준][Java] 6186 - Best Grass

목차

 

문제 정보

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

6186번: Best Grass

난이도 : S5

유형 : BFS, DFS

---

문제 풀이

상하좌우로 최대 2개씩 붙어있는 잔디를 찾아주면 된다.

(문제에서 상하좌우로 최대 2개씩만 붙어있음을 언급)

 

탐색 방법은 스탠다드한 BFS기법을 이용하였다.

 

(0,0)에서 차례대로 (N-1, N-1)까지 이중 포문을 이용하여 한 번씩 접근하여

탐색하지 않았고 그 자리에 잔디가 있으면 BFS탐색을 해주었다.

BFS 메소드가 실행될 때마다 1씩 카운팅 해주면 된다.

---

코드

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

public class Main {

    private final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int R, C;
    private char[][] map;
    private boolean[][] isVisited;
    private int res;

    public void bfs(int r, int c) {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{r, c});
        isVisited[r][c] = true;

        while (!que.isEmpty()) {
            int[] cur = que.poll();
            for (int k = 0; k < 4; k++) {
                int nX = cur[0] + dir[k][0];
                int nY = cur[1] + dir[k][1];

                if (nX < 0 || nX >= R || nY < 0 || nY >= C) {
                    continue;
                }
                if (isVisited[nX][nY]) {
                    continue;
                }
                if (map[nX][nY] != '#') {
                    continue;
                }

                isVisited[nX][nY] = true;
                que.add(new int[]{nX, nY});
            }
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        res = 0;
        isVisited = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '#' && !isVisited[i][j]) {
                    res++;
                    bfs(i, j);
                }
            }
        }

        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}