[C++] 백준 1012. 유기농 배추

문제 설명

직사각형 형태의 밭의 각 좌표마다 배추가 심어질 수 있다. 배추가 심어지면 1로 표현한다. 1로 이어진 구역이 몇 개인지 세는 문제다.

 

접근

직사각형 형태의 밭은 2차원 배열로 표현할 수 있다.

2차원 배열 상에서 이어진 1은 DFS나 BFS를 이용해 탐색할 수 있다.

DFS나 BFS로 구역을 탐색하고, 한 구역의 탐색이 끝나면 벌레 개수를 증가시킨다.

모든 구역이 탐색될 때까지 반복한다.

 

구현

DFS를 이용하기로 한다.

static int dx[] = { 0, 1, 0, -1 };
static int dy[] = { 1, 0, -1, 0 };

void DFS(int x, int y) {
	visited[x][y] = true;

	// 상하좌우 네 방향으로 이동
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		// 범위를 벗어나지 않고, 배추가 있으며, 아직 방문하지 않았다면 DFS 재귀 호출
		if (nx >= 0 && nx < M && ny >= 0 && ny < N && farm[nx][ny] == 1 && !visited[nx][ny]) {
			DFS(nx, ny);
		}
	}
}

 

dx와 dy는 좌표에서 상하좌우로 이동하기 위한 변수다. 

현재의 x좌표에 dx[0]과 dy[0]을 더하면 y값이 1 증가되어 오른쪽으로 이동한다. 4번 반복하면 상하좌우로 한 번씩 이동하는 셈이다. 

 

밭 안에서 움직여야 하므로, if문으로 밭의 범위를 벗어나지 않도록 지정한다. 또한 좌표값이 1이고(배추가 있고), 방문하지 않은 상태라면 이 위치에서 DFS를 재귀호출해 이어진 영역을 탐색한다.

 

memset(farm, 0, sizeof(farm));
memset(visited, 0, sizeof(visited));

 

테스트케이스 개수를 입력받는 문제이므로 각 테스트케이스가 진행될 때마다 배추밭과 방문배열을 초기화해야 한다.

memset을 이용하면 2차원 배열을 초기화할 수 있다. visited는 bool 타입인데, C++에서 false와 0은 동일한 값이므로 memset을 이용할 수 있다. 

 

//배추밭 전체를 돌며 DFS 수행
for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		if (farm[i][j] == 1 && !visited[i][j]) {
			DFS(i, j); // 새로운 구역을 찾음
			count++; // 벌레 수 증가
		}
	}
}

 

전체 좌표를 돌면서 DFS를 수행한다. 좌표값이 1이고 방문하지 않았다면 DFS를 수행해 구역을 찾는다. DFS가 종료되면 구역 탐색이 끝난 것이므로 count를 증가시킨다. 

 

한 구역 탐색이 끝나면 처음 탐색을 시작한 위치로 되돌아오는데, 여기서 다시 탐색을 시작한다 해도 자신의 구역은 visited 배열이 false로 바뀐 상태이므로 중복은 발생하지 않는다. 

전체 코드

#include <iostream>
#include <cstring>
using namespace std;

static int dx[] = { 0, 1, 0, -1 };
static int dy[] = { 1, 0, -1, 0 };
int farm[50][50];	//배추밭
bool visited[50][50];	//방문기록
int M, N; //가로, 세로

void DFS(int, int);

/*
시작하는 점은 0,0
만약 정점의 값이 1이라면 큐에 추가
큐에서 내보내면 해당 위치 0으로 없앰x
큐가 비었으면 해당 구역 처리했으므로 count++
다음구역은 그냥 0,0부터 다시 시작해서 값이 1이고 visited는 false인 정점을 찾으면 다시 BFS 시작 

 */

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;	//테스트케이스
	int k;	//배추 개수
	


	//테스트케이스 수 입력받기
	cin >> t;

	for (int i = 0; i < t; i++) {
		//값 입력
		cin >> M >> N >> k;

		//배열 초기화
		memset(farm, 0, sizeof(farm));
		memset(visited, 0, sizeof(visited));


		for (int i = 0; i < k; i++) {
			int x, y;	//배추의 좌표
			cin >> x >> y;
			farm[x][y] = 1;
		}

		int count = 0;

		//배추밭 전체를 돌며 DFS 수행
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (farm[i][j] == 1 && !visited[i][j]) {
					DFS(i, j); // 새로운 구역을 찾음
					count++; // 벌레 수 증가
				}
			}
		}
		
		cout << count << endl;
	}

	return 0;
}

void DFS(int x, int y) {
	visited[x][y] = true;

	// 상하좌우 네 방향으로 이동
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		// 범위를 벗어나지 않고, 배추가 있으며, 아직 방문하지 않았다면 DFS 재귀 호출
		if (nx >= 0 && nx < M && ny >= 0 && ny < N && farm[nx][ny] == 1 && !visited[nx][ny]) {
			DFS(nx, ny);
		}
	}
}