[Baekjoon 6186] Best Grass - JAVA

[Silver IV] Best Grass - 6186

문제 링크

성능 요약

메모리: 14108 KB, 시간: 124 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현

문제 설명

Bessie is planning her day of munching tender spring grass and is gazing out upon the pasture which Farmer John has so lovingly partitioned into a grid with R (1 <= R <= 100) rows and C (1 <= C <= 100) columns. She wishes to count the number of grass clumps in the pasture.

Each grass clump is shown on a map as either a single '#' symbol or perhaps two '#' symbols side-by-side (but not on a diagonal). No two symbols representing two different clumps are adjacent. Given a map of the pasture, tell Bessie how many grass clumps there are.

By way of example, consider this pasture map where R=5 and C=6:

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

This pasture has a total of 5 clumps: one on the first row, one that spans the second and third row in column 2, one by itself on the third row, one that spans columns 4 and 5 in row 4, and one more in row 5.

입력

• Line 1: Two space-separated integers: R and C
• Lines 2..R+1: Line i+1 describes row i of the field with C characters, each of which is a '#' or a '.'

출력

• Line 1: A single integer that is the number of grass clumps Bessie can munch

문제 풀이

문제를 간단하게 요약하면 아래와 같다.

풀 밭은 R행과 C열로 이루어져있다.

각 위치는 '#' 또는 '.' 으로 표시되며, '#'은 풀 덩어리를 나타낸다.

풀 덩어리는 하나의 '#' 또는 인접한 두 개의 '#'가 나란히 있는 경우가 해당된다.
이때, 대각선 방향은 덩어리로 인정하지 않는다.

DFS를 사용하면 쉽게 풀이가 가능하다.

로직은 아래와 같다.

아직 방문하지 않은 '#'인 위치를 찾으면, 해당 위치에서 DFS를 통해 연결된 모든 '#'을 탐색하여 하나의 풀 덩어리로 처리한다.

탐색이 끝나면 다음 아직 방문하지 않은 '#'을 찾아서 같은 방식으로 처리한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int rowCount = Integer.parseInt(st.nextToken());
        int colCount = Integer.parseInt(st.nextToken());
        int specialCount = 0;

        char[][] field = new char[rowCount][colCount];
        boolean[][] isSpecial = new boolean[rowCount][colCount];

        for (int i = 0; i < rowCount; i++) {
            String rowInput = br.readLine();
            for (int j = 0; j < colCount; j++) {
                field[i][j] = rowInput.charAt(j);
            }
        }

        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < colCount; j++) {
                if (field[i][j] == '#') {
                    field[i][j] = '.';
                    if (i > 0 && field[i - 1][j] == '#') {
                        isSpecial[i - 1][j] = true;
                    }
                    if (i < rowCount - 1 && field[i + 1][j] == '#') {
                        isSpecial[i + 1][j] = true;
                    }
                    if (j > 0 && field[i][j - 1] == '#') {
                        isSpecial[i][j - 1] = true;
                    }
                    if (j < colCount - 1 && field[i][j + 1] == '#') {
                        isSpecial[i][j + 1] = true;
                    }
                    if (!isSpecial[i][j]) {
                        specialCount++;
                    }
                }
            }
        }

        System.out.println(specialCount);
    }
}

코드 풀이

        int rowCount = Integer.parseInt(st.nextToken());
        int colCount = Integer.parseInt(st.nextToken());
        int specialCount = 0;

        char[][] field = new char[rowCount][colCount];
        boolean[][] isSpecial = new boolean[rowCount][colCount];

• rowCount, colCount: 주어진 R행과 C열을 저장할 변수
• specialCount: 특별한 칸을 세기 위한 변수, 초기값을 0으로 설정
• field: 입력으로 받은 문자들을 저장할 용도로 사용될 배열
• isSpecial: 특별한 칸인지 여부를 표시하는 용도로 사용될 배열

for (int i = 0; i < rowCount; i++) {
    String rowInput = br.readLine();
    for (int j = 0; j < colCount; j++) {
        field[i][j] = rowInput.charAt(j);
    }
}

• 입력으로 들어온 문자열을 field 배열에 저장한다.

for (int i = 0; i < rowCount; i++) {
    for (int j = 0; j < colCount; j++) {
        if (field[i][j] == '#') {
            field[i][j] = '.';
            if (i > 0 && field[i - 1][j] == '#') {
                isSpecial[i - 1][j] = true;
            }
            if (i < rowCount - 1 && field[i + 1][j] == '#') {
                isSpecial[i + 1][j] = true;
            }
            if (j > 0 && field[i][j - 1] == '#') {
                isSpecial[i][j - 1] = true;
            }
            if (j < colCount - 1 && field[i][j + 1] == '#') {
                isSpecial[i][j + 1] = true;
            }
            if (!isSpecial[i][j]) {
                specialCount++;
            }
        }
    }
}

• field 배열을 순회하면서 각 위치의 문자가 '#'인 경우를 처리한다.
• '#'를 '.'로 변경하고, 그 주변의 칸들을 isSpecial 배열에 특별한 칸으로 표시한다.
• 현재 위치가 특별한 칸이 아닌 경우에만 specialCount를 증가시킨다.

System.out.println(specialCount);

• 풀 덩어리의 개수인 specialCount를 출력한다.