백준 1012번. 유기농 배추 (C++)

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

 

풀이

#include <iostream>
#include <vector>

using namespace std;

// 최대 사이즈 : 50*50
#define MAX 51

// 유기농 배추 저장할 2차원 배열
int cabbage[MAX][MAX];
// 유기농 배추 방문 여부 저장할 2차원 배열
bool visited[MAX][MAX];

// 총 4방향으로 이동할 수 있음 (여기서는 좌,우,하,상 순서)
int coX[] = {-1, 1, 0, 0}; // x좌표
int coY[] = {0, 0, -1, 1}; // y좌표

// 결과 값
int answer = 0;
vector< int > v;

// dfs로 인접하는 필요한 배추흰지렁이의 개수 찾기 (재귀로 문제 풀이)
void dfs (int x, int y) {
  // 함수 안으로 들어온 순간 방문한 것이 되므로, 해당 땅의 좌표는 true
  visited[x][y] = true;

  // 총 4방향으로 이동 가능하므로 4번 순회
  for (int i = 0; i < 4; i++) {
    // x,y를 좌,우,하,상으로 움직임
    int px = x + coX[i];
    int py = y + coY[i];

    // 이동한 좌표가 0보다 커야하고(음수면 범위를 벗어난 것이 됨), 방문을 하지 않았어야하며, 1이어야 함 (0이면 탐색할 필요x)
    if (px >= 0 && py >= 0 && !visited[px][py] && cabbage[px][py] == 1) {
      // 조건 만족시 재귀 호출
      dfs(px, py);
    }
  }
}

int main()
{
  // 테스트 케이스 개수 입력받기
  int T;
  cin >> T;

  int M, N, K; // 순서대로 가로, 세로, 배추 개수
  // 테스트 케이스 개수만큼 반복
  for (int i = 0; i < T; i++) {
    cin >> M >> N >> K;

    // 결과 값 0으로 초기화
    answer = 0;
    
    // N * M 이므로 N * M만큼 반복하며 유기농 배추 값, visited 값 초기화 (2차원 배열은 수학이랑 다르게 y,x 순서로 사용)
    for (int ci = 0; ci < N; ci++) {
      for (int cj = 0; cj < M; cj++) {
        cabbage[ci][cj] = 0;
        visited[ci][cj] = false;
      }
    }

    int x, y;
    
    // K개 만큼 반복 (값이 1인 배추 설정을 위해)
    for (int j = 0; j < K; j++) {
      // 1인 곳 입력 받고, cabbage 배열에 값 세팅
      cin >> x >> y;
      cabbage[y][x] = 1;
    }

    for (int n = 0; n < N; n++) {
      for (int m = 0; m < M; m++) {
        // n, m이 방문하지 않은 좌표이고 cabbage[n][m]이 1이면 dfs 함수 호출
        if (!visited[n][m] && cabbage[n][m] == 1) {
          dfs(n, m);
          // dfs 함수 끝나고 나서 answer를 하나씩 늘려줌
          answer++;
        }
      }
    }

    v.push_back(answer);
  }

  // 결과 값 출력
  for (int i = 0; i < v.size(); i++) {
    cout<< v.at(i) << endl;
  }
  return 0;
}