BOJ 6186 - Best Grass

문제

R x C 격자에서 #으로 표시된 풀밭의 연결 요소(상하좌우 인접) 개수를 구하라.

입력

행 수 R, 열 수 C, 이후 R x C 격자가 주어진다. #은 풀, .은 빈 칸이다.

출력

연결된 풀밭 영역의 수를 출력한다.

예제

입력	출력
`5 6` `..#...` `...#..` `..##..` `..#...` `......`	`2`

풀이

격자를 순회하며 미방문 # 칸에서 DFS를 시작하여 연결 요소 수를 센다.

격자를 입력받아 # 칸을 1, . 칸을 0으로 표시한다
모든 칸을 순회하며 값이 1인 칸에서 DFS를 시작한다
DFS에서 방문한 칸은 0으로 표시하여 재방문을 방지한다
DFS 시작 횟수가 연결 요소 수이다

핵심 아이디어: 표준적인 연결 요소 카운팅 문제로, DFS/BFS로 각 영역을 탐색하며 개수를 센다.

코드

#include <iostream>
using namespace std;
 
char rc[101][101];
int rc2[101][101];
int r, c;
 
int dfs(int a, int b)
{
  rc2[a][b] = 0;
  int nx[4] = {0, 0, -1, 1};
  int ny[4] = {1, -1, 0, 0};
  for (int i = 0; i < 4; i++)
  {
    if (rc2[a + nx[i]][b + ny[i]] == 1 && 0 < a + nx[i] && a + nx[i] <= r && 0 < b + ny[i] && b + ny[i] <= c)
    {
      dfs(a + nx[i], b + ny[i]);
    }
  }
  return 0;
}
 
int main()
{
  int i, j, k = 0;
  cin >> r >> c;
  for (i = 1; i <= r; i++)
  {
    for (j = 1; j <= c; j++)
    {
      cin >> rc[i][j];
      if (rc[i][j] == '.')
      {
        rc2[i][j] = 0;
      }
      if (rc[i][j] == '#')
      {
        rc2[i][j] = 1;
      }
    }
  }
  for (i = 1; i <= r; i++)
  {
    for (j = 1; j <= c; j++)
    {
      if (rc2[i][j] == 1)
      {
        dfs(i, j);
        k++;
      }
    }
  }
  cout << k;
  return 0;
}

복잡도

시간: O(R * C)
공간: O(R * C)

문제