[백준] 1012번 문제 풀이

문제

www.acmicpc.net/problem/1012

1012번: 유기농 배추

풀이

배열에 값을 입력받고 반복문을 돌면서 조건이 맞으면 dfs함수를 실행한다.

#include <iostream>
using namespace std;
int N, M, C;
int cnt;
int arr[51][51];
bool check[51][51];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

void init()
{
  cnt = 0;
  for (int i = 0; i <= M; i++)
  {
    for (int j = 0; j <= N; j++)
    {
      arr[i][j] = 0;
      check[i][j] = false;
    }
  }
}

void dfs(int x, int y)
{
  // 현재 좌표에서 상, 하, 좌, 우를 전부 살피는 용도의 반복문
  for (int i = 0; i < 4; i++)
  {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // 배열 밖으로 나가지 않는지 검사
    if (nx < 0 || nx >= M || ny < 0 || ny >= N)
      continue;
    // 방문하지 않았거나 arr[nx][ny]에 1이 있다면 방문했다고 표시 후 재귀 호출 수행
    if (!check[nx][ny] && arr[nx][ny])
    {
      check[nx][ny] = true;
      dfs(nx, ny);
    }
  }
}

int main()
{
  int t, a, b;
  cin >> t;
  for (int i = 0; i < t; i++)
  {
    // 배열 및 카운팅 변수 초기화
    init();
    cin >> M >> N >> C;
    for (int j = 0; j < C; j++)
    {
      cin >> a >> b;
      arr[a][b] = 1;
    }
    // 반복문을 돌면서 방문하지 않았던 배열이 있을 경우 dfs를 실행
    // 그리고 카운팅 변수를 1을 더한뒤에 방문했다는 표시
    for (int j = 0; j < M; j++)
    {
      for (int k = 0; k < N; k++)
      {
        if (!check[j][k] && arr[j][k])
        {
          cnt++;
          check[j][k] = true;
          dfs(j, k);
        }
      }
    }
    cout << cnt << "\n";
  }
  return 0;
}

여담

음... 이전에 비슷한 문제를 풀어봤어서 처음 그래프 이론 문제를 접했을 때보다는 수월하게 풀었다.

값을 어떻게 입력받는지, 반복문을 돌면서 각 방에 접근하는지 등... 진작에 이렇게 공부를 했어야 한다.