[백준] 1012번: 유기농 배추 - c++

유기농 배추

문제

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

예제

문제 정의

🔑 key

이 문제를 풀 땐 memset의 사용법에 대해 알게되었다.
memset이란 배열을 초기화해주는 함수이다.

memset(adj, 0, sizeof(adj));

memset(초기화하기싶은 배열명, 초기화 하고싶은 값, 배열 크기); 와 같이 할당하면 된다.

나는 adj라는 배열에 있는 모든 값을 0으로 초기화하고 싶어서 위와 같이 사용했다.

---

문제를 읽어보면 전형적인 연결요소의 개수를 구하는 문제임을 알 수 있다. 연결요소의 개수를 구할 때는 보통 dfs를 사용하면 편리하게 구할 수 있다.

dfs를 한바퀴 돌 때마다 cnt(연결요소의 개수)의 값에 +1을 해주면 된다.

#include<bits/stdc++.h>
using namespace std;
// 연결요소 개수 찾기, 인접리스트
const int max_size = 54;
int a, b;
int t, m, n, k, adj[max_size][max_size], visited[max_size][max_size];
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x) {
  visited[y][x] = 1;
  for (int i = 0; i < 4; i++)
  {
    int ny = y + dy[i];
    int nx = x + dx[i];
    if (ny<0 || ny>=n || nx<0 || nx>=m || visited[ny][nx]) continue;
    if (adj[ny][nx] == 0) continue;
    dfs(ny, nx);
  }
  return;
}
int main() {
  cin >> t;
  for (int i = 0; i < t; i++) {
    int cnt = 0;
    cin >> m >> n >> k;
    memset(adj, 0, sizeof(adj));
    memset(visited, 0, sizeof(visited));

    for (int j = 0; j < k; j++)
    {
      cin >> a >> b;
      adj[b][a] = 1;
    }
    for (int t = 0; t < n; t++) {
      for (int r = 0; r < m; r++) {
        if (!visited[t][r] && adj[t][r] == 1) {
          cnt++;
          dfs(t, r);
        }
      }
    }
    cout << cnt << "\n";
  }
}