[백준 알고리즘] 1012번 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

문제

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

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

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

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 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

입력

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

출력

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

풀이

일단 이 문제에는 배추가 어디에 심어져있는지 탐색을 해야 한다. 즉 모든 구역을 탐색해야 하므로 DFS 알고리즘을 활용한다.

Stack과 재귀함수를 이용할 수 있으며 그 중 이 문제 정답으로는 재귀함수를 이용하였다

 

DFS

- 배추가 있는 구역을 탐색한다.

1) 이미 방문한 곳이라면 종료

2) 방문 하지 않는 곳이라면 계속 탐색한다.

  
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stack>
#include<vector>

using namespace std;

int x; // row
int y; // clumn
int point = 0;

//int **visitField = new int*[50];
//int **Field = new int*[50];

int visitField[50][50] = { 0 };
int Field[50][50] = { 0 };

int Array_Y[4] = { -1,0,1,0 };
int Array_X[4] = { 0,-1,0,1 };


void DFS(int startY, int startX) { //x좌표 y좌표

	//cout << startY << "," << startX << endl;

	visitField[startY][startX] = true;

	for (int i = 0; i < 4; i++) {


		int Direction_Y = startY + Array_Y[i];
		int Direction_X = startX + Array_X[i];


		//우리가 가려는 범위가 기존 밭의 범위를 벗어난다면
		if(Direction_X >= 0 && Direction_Y >= 0 && Direction_X < x && Direction_Y < y) {
				
                //해당 구역에 배추가 심어져있거나 방문하지 않았을 때 DFS 실행! (재귀함수)
			if (Field[Direction_Y][Direction_X] ==1 && visitField[Direction_Y][Direction_X] == false) {

				visitField[Direction_Y][Direction_X] = true;

				DFS(Direction_Y, Direction_X);

			}

		}

	}



}

int main() {

	int term;

	cin >> term;

	while (term--) {

		//중복된다. 다시 시도할 것


		cin >> x >> y >> point;
		int count = 0;




	//초기화
		for (int i = 0; i < x; i++) {

			for (int j = 0; j < y; j++) {

				visitField[i][j] = 0; 
				Field[i][j] = 0;
			}
		}



		for (int j = 0; j < point; j++) {

			int tempX=0;
			int tempY=0;

			cin >> tempX >> tempY;
			Field[tempY][tempX] = 1;

		}

		/*
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++){
				cout << Field[i][j] << " ";
			}
			cout << endl;
		}
		*/


		for (int i = 0; i < x; i++){
			for (int j = 0; j < y; j++)
			{
				if (Field[j][i] == 1 && visitField[j][i] == false) {

					DFS(j, i);
					count++; // 해당 시작점의 DFS가 모두 종료되었을 때 필요한 흰지렁이의 수(Count) 증가.
					//cout << "count 끝" << endl;
				}
			}
		}


		cout << count << endl;

	}

}

 

끝.