백준 유기농 배추

해당 문제는 백준온라인 저지에서 나온 문제입니다.

해결 방식

깊이 우선 탐색 알고리즘(DFS)을 베이스로 작성하였습니다.

해결 방식을 고른 이유

너비 우선 탐색 알고리즘은 최적의 해를 찾기 유용하지만, 그만큼 비용이 많이들어가며, 형제인 모든 노드를 탐색하기때문에 상대적으로 시간이 많이걸립니다.
깊이 우선 탐색은 상대적으로 구현이 간단하고, 목표 노드가 깊은 곳에 있을 경우 빠른 속도로 해를 구할 수 있습니다. 단점으로는 주변 모든 노드를 탐색하는것이 아니라 자신이 선택한 뎁스에서만 탐색을 진행하기 때문에, 얻어진 해가 최적의 결과가 아닐 수가 있습니다.

해당 문제는 깊이우선탐색으로도 최적의 해를 구할 수 있으며, 구현이 간단하기에 이를 선택하였습니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int map[50][50] = { 0, };
int mask[50][50] = { 0, };
int	dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };//이동할 방향
int M, N, K;
void	clear_map(int width, int height)
{
	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			map[i][j] = 0;
			mask[i][j] = 0;
		}
	}
}

void	solution(int x, int y)
{
	if (map[y][x] == 0)//배추가 존재한다면
		return;
	if (mask[y][x] == 0)//처음 지나가는 배추일 경우.
		mask[y][x] = 1;//다음번 탐색에서 제외
	for (int i = 0; i < 4; i++)
	{
		if ((x + dir[i][0] >= M || y + dir[i][1] >= N) || (x + dir[i][0] < 0 || y + dir[i][1] < 0))//이동할 경로가 맵의 범위를 벗어나는 경우
			continue;
		if (mask[y + dir[i][1]][x + dir[i][0]] == 1)//해당 경로에 배추가 있는지
			continue;
		mask[y + dir[i][1]][x + dir[i][0]] == 1;
		solution(x + dir[i][0], y + dir[i][1]);
	}
}
int main()
{
	int T;
	cin >> T;
	vector<int> answer;

	for (int t_case = 0; t_case < T; t_case++)
	{
		//init start
		int x, y;
		int cnt = 0;
		cin >> M >> N >> K;
		clear_map(M, N);

		for (int i = 0; i < K; i++)
		{
			cin >> x >> y;
			map[y][x] = 1;
		}
		//init end
		for (int y = 0; y < N; y++)
		{
			for (int x = 0; x < M; x++)
			{
				if (map[y][x] == 1 && mask[y][x] == 0)
				{
					solution(x, y);
					cnt++;
				}
			}
		}
		answer.push_back(cnt);
	}
	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << endl;
}

코드 해설

핵심적인 부분은 solution 부분입니다.

DFS 알고리즘을 활용하여, 재귀를 돌며 조건에 맞을 때까지 탐색을 진행합니다.
map은 배추밭 농장을 의미하고, mask는 이미 탐색한 경로를 의미합니다.
mask가 필요한 이유는 이미 지나온 노드를 한번 더 탐색하는 것을 방지하기 위한 것인데,

만약 지나온 곳을 적어놓지 않는다면, 0,0번째 배열에서 탐색을 진행하고, 0,1번째 배열에서 또다시 탐색을 진행할 것입니다. 이런 문제를 방지하기 위해 mask라는 이중배열을 선언하여 지나온 곳을 적어놓아 다음번 탐색에서 제외해놓는 겁니다.