[코딩테스트] 백준 - Best Grass

Best Grass 6186번 [14일차]

시간제한	메모리 제한
1초	128MB

문제

베시는 부드러운 봄 풀을 씹는 하루를 계획하고 있으며, 농부 존이 R(1 <= R <= 100) 행과 C(1 <= C <= 100) 열로 사랑스럽게 구획한 목초지를 바라보고 있습니다. 그녀는 목초지에 있는 풀 덩어리의 수를 세고 싶어합니다.

각 풀 덩어리는 지도에 단일 '#' 기호 또는 두 개의 '#' 기호가 나란히(대각선은 아님) 표시됩니다. 두 개의 다른 덩어리를 나타내는 두 개의 기호가 인접하지 않습니다. 목초지 지도가 주어지면 Bessie에게 풀 덩어리가 몇 개 있는지 말하세요.

예를 들어, R=5, C=6인 이 목초지 지도를 고려해 보겠습니다.

.#....
..#...
..#..#
...##.
.#....

이 목초지에는 총 5개의 덩어리가 있습니다. 첫 번째 줄에 하나, 2열에서 2번째와 3번째 줄에 걸쳐 있는 덩어리, 세 번째 줄에 혼자 있는 덩어리, 4열에서 4번째와 5번째 줄에 걸쳐 있는 덩어리, 그리고 5열에 하나 더 있습니다.

 

입력

• 1번째 줄: 공백으로 구분된 두 정수: R과 C
• 2번째 줄..R+1: i번째 줄은 C개의 문자로 필드의 i번째 행을 설명하는데, 각각은 '#' 또는 '.'입니다.

 

출력

1번째 줄: Bessie가 먹을 수 있는 풀 덩어리의 수를 나타내는 단일 정수

 

나의코드

package day14;

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

// Best Grass - 6186번
public class Solution1 {
    static boolean[][] used;
    // 방문 체크 확인

    public static void main(String[] args) throws IOException {
        // 너비우선탐색 BFS
        // 상하좌우 탐색 #이 있는지 확인
        // 없다면 이어진 목초지 덩어리가 없으니까 count++

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stNum = new StringTokenizer(br.readLine());
        int X = Integer.parseInt(stNum.nextToken());
        int Y = Integer.parseInt(stNum.nextToken());

        int[][] arr = new int[X][Y];
        used  = new boolean[X][Y];

        // 입력받은 문자 배열에 넣어주기  # 이 있을경우 1로 / 아닐경우 0으로 넣어주기
        for(int i = 0;i<X;i++){
            String line = br.readLine();
            for(int j=0;j<line.length();j++){
                Character c = line.charAt(j);
                if(c == '#'){
                    arr[i][j] = 1;
                }else{
                    arr[i][j] = 0;
                }

            }
        }
        int count = 0;
        for(int i = 0;i<X;i++) {
            for (int j = 0; j < Y; j++) {
                // #이 있고, 방문했던 곳이 아닐경우 탐색
                if(arr[i][j] == 1 && !used[i][j]){
                    count++;
                    dfs(i,j,arr);
                }
            }
        }
        System.out.println(count);
    }

    static void dfs(int x, int y, int[][] num){
        used[x][y] = true;

        //입력받은 행과 열의 범위를 넘어가면안됨!

        // 상
        if (x + 1 < num.length && num[x + 1][y] == 1 && !used[x + 1][y]) {
            dfs(x + 1, y, num);
        }

        // 하
        if (x - 1 >= 0 && num[x - 1][y] == 1 && !used[x - 1][y]) {
            dfs(x - 1, y, num);
        }

        // 좌
        if (y - 1 >= 0 && num[x][y - 1] == 1 && !used[x][y - 1]) {
            dfs(x, y - 1, num);
        }

        // 우
        if (y + 1 < num[0].length && num[x][y + 1] == 1 && !used[x][y + 1]) {
            dfs(x, y + 1, num);
        }


    }

}

 
DFS로 탐색하는 문제이다
사실 BFS로 풀어도 상관없기는 하다
boolean배열 꼭 필요!
기본 개념으로는 위/ 아래/ 좌/ 우 로 탐색을 해야하나 사실 우/ 아래만 탐색해도 괜찮다
판을 넘어가지 않도록 조건을 잘 맞춰주는것도 중요한 문제다!