어떤 문제인가?

DFS를 이용하여 전체 탐색을 하는 문제.

시행착오 횟수

한 번에 성공함.

1차 시도: AC

2667번 문제 풀이에서 고배를 마시고 온 탓에, 이 문제는 상대적으로 쉽게 느껴졌다. 바로 본론으로 넘어가자.

#include <stdio.h>

int M, N;
int count = 0;
int table[50][50];
int visited[50][50];

void dfs(int x, int y) {
  if (x < 0 || x >= M || y < 0 || y >= N || table[x][y] == 0 ||
      visited[x][y] == 1)
    return;

  visited[x][y] = 1;
  count++;
  dfs(x + 1, y);
  dfs(x - 1, y);
  dfs(x, y + 1);
  dfs(x, y - 1);
}

void clear() {
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
      table[i][j] = 0;
      visited[i][j] = 0;
    }
  }
}

int main() {
  int T, K;
  scanf("%d", &T);

  for (int i = 0; i < T; i++) {
    scanf("%d%d%d", &M, &N, &K);
    clear();

    for (int i = 0; i < K; i++) {
      int X, Y;
      scanf("%d%d", &X, &Y);
      table[X][Y] = 1;
    }

    int farmCount = 0;
    for (int j = 0; j < M; j++) {
      for (int k = 0; k < N; k++) {
        count = 0;
        dfs(j, k);
        if (count > 0)
          farmCount++;
      }
    }

    printf("%d\n", farmCount);
  }

  return 0;
}

2667번 문제와 다른 점이라면, 이 문제는

• 2667번 문제의 '총 단지 수'에 대응되는 '필요한 배추흰지렁이 수'만을 구하면 된다.
• 여러개의 테스트케이스가 존재한다.

테스트케이스는 반복문으로 구현하면 되니, 남은 건 '배추흰지렁이 수'를 구하는 것 뿐이고 이는 2667번 문제에서 이미 풀어보았기 때문에 어렵지 않게 풀 수 있었다.

개선할 부분

• visited 는 사실 쓸 필요가 없었다.
  -> table의 한 지점이 만약 1이라면, 방문 후 0으로 만들어버려 나중에 탐색하지 못하도록 하는 방법도 먹힌다.
• table 는 memset() 함수만으로 전부 0으로 초기화할 수 있다.
• 비유를 들자면 '덩어리'의 한 지점을 짚기만 하면 되므로, 별도의 count 함수를 둘 필요 없이, 현재 지점이 덩어리의 일부라면 farmCount를 1 올리고 바로 dfs를 수행해서 그 덩어리를 지워버리면 된다.