[Beakjoon Online Judge] 1012 - 유기농 배추

I 문제 소개

---

문제

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

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

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

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

 

출력

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

---

II 문제 풀이

---

이 문제로 말하자면, 땅 세기 문제라고 할 수 있다.

우리의 눈은 문제에 예시로 있는 표를 보면 '딱봐도 5개네~'라고 바로 인식하지만, 컴퓨터는 눈이 없어 값 하나 하나 따로 불러서만 볼 수 있다.

그러면 1(배추)을 지나갈 수 있는 길이라고 생각하고, 0(땅)을 벽이라고 생각해보자. 연결되어 있는 길을 하나의 길이라고 하면, 그 길이 몇 개인지 세는 것이 이 문제의 답이다. 따라서 상하좌우를 살피며 길을 최대한 탐색해 방문하지 않은 길이 없게 하고, 그 탐색 과정을 총 몇 번 했는지 세면 되지 않을까? 이것이 문제의 핵심이고, 우리는 이 과정을 DFS라고 부른다.

 

DFS에 대해 부연 설명을 하자면, 직역하면 깊이 우선 탐색(Depth First Search)으로, 미로찾기를 예시로 들었을 때 갈림길에서 한 길을 선택해 막다른길이 나올 때까지 이동하고 다시 갈림길로 돌아와서 다른 길로 이동하는 방법이다.

물론 그 경로가 최단 경로라는 보장은 없지만, 최단 경로를 알 수 있는 BFS라는 방법에 비해 훨씬 적은 메모리로 탐색할 수 있다는 장점이 있다.

 

0. 초기 환경 설정

---

#include <iostream>

using namespace std;

int farm[52][52];
int fcache[52][52];

int main(void)
{
	int T, M, N, K, X, Y;
	int ans;
	cin >> T;
	for (int i = 0;i < T;i++)
	{
		cin >> M >> N >> K;
		// Todo : Init
		for (int i = 0;i < K;i++)
		{
			cin >> X >> Y;
			farm[Y+1][X+1] = 1;
		}
		// Todo : DFS
		cout << ans << endl;
	}
	return 0;
}

문제에 표가 있듯이 이것을 이차원 배열의 형태로 나타낼 생각이다.

한 정점에서 상, 하, 좌, 우의 값을 읽을 것이기 때문에 그 정점이 모서리에 있는 경우 음수의 인덱스로 접근할 수 있어 경우를 나눠줘야하는데, 귀찮은 일이기 때문에 아예 테두리 한 칸을 만들어 그런 일이 발생하지 않게 어디서든 상하좌우를 읽을 수 있게 만들고 싶었다.

따라서 문제에서 정해준 최대 길이인 50칸보다 테두리 한 칸이 더 많은 farm[][]이라는 배열을 만들었고, DFS 과정에서 방문했던 좌표를 기억해놓을 fcache[][]라는 배열을 만들었다.

문제에서 말하는 X, Y좌표는 X가 가로, Y가 세로인 좌표인데, 이차원 배열에서 첫번째 인덱스는 행이고 두번째 인덱스는 열이기 때문에 순서를 바꿔서 입력을 받아야 한다.

 

1. 배열 초기화

---

void initFarm()
{
	for (int i = 0;i < 52;i++)
	{
		for (int j = 0;j < 52;j++)
		{
			farm[i][j] = 0;
			fcache[i][j] = 0;
		}
	}
}

테스트 케이스가 여러 개이기 때문에 각 케이스마다 초기화를 해줘야해서 초기화 함수를 작성했다.

 

2. DFS

---

int searchLand(int x, int y)
{
	int fup = farm[x - 1][y];
	int fdown = farm[x + 1][y];
	int fleft = farm[x][y - 1];
	int fright = farm[x][y + 1];

	int cup = fcache[x - 1][y];
	int cdown = fcache[x + 1][y];
	int cleft = fcache[x][y - 1];
	int cright = fcache[x][y + 1];

	fcache[x][y] = 1; // 방문 기록 저장

	if (fup + fdown + fleft + fright == 0) // 1칸짜리 땅이라면
		return 0;
	if (fup == cup && fdown == cdown && fleft == cleft && fright == cright) // 주변을 모두 방문했다면
		return 0;
	if (fup == 1 && cup == 0)
		searchLand(x - 1,y);
	if (fdown == 1 && cdown == 0)
		searchLand(x + 1, y);
	if (fleft == 1 && cleft == 0)
		searchLand(x, y - 1);
	if (fright == 1 && cright == 0)
		searchLand(x, y + 1);
	return 0;
}

사실 함수를 void로 짜야했는데 처음에 함수를 다른 방식으로 짜서 바꾸는 것을 깜빡했다.

int로 짠 김에 return 0으로 함수를 종료하게 만들었고, 상-하-좌-우로 이동이 가능한데 방문한 적이 없을 경우 재귀로 호출해서 이동하게 만들었다. 이 재귀하는 구조가 DFS라고 할 수 있다.

 

여담이지만 요새 리액트를 공부하면서 코드 가독성의 중요성을 느껴서 변수 하나하나를 따로 만들어보았다. 가독성 외에 큰 의미는 없다.

 

3. DFS 호출

---

for (int i = 1;i <= N;i++)
{
	for (int j = 1;j <= M;j++)
	{
		if (farm[i][j] == 1)
		{
			if (fcache[i][j]==0)
			{
				searchLand(i, j);
				ans += 1;
			}
			else
				continue;
		}
		else
			continue;
	}
}

main 함수에서 DFS를 호출하는 부분이다.

모든 정점을 방문하면서, 이 부분이 길이면서 방문한적 없는 곳이라면 이 부분부터 DFS를 시작하게 했다. 그러면서 DFS를 한 번 할 때마다의 횟수를 ans라는 변수에 저장했다.

M이 가로의 길이이고 N이 세로의 길이이기 때문에 j는 M으로 제한해야하고 i는 N으로 제한해야한다.

 

4. 최종

---

#include <iostream>

using namespace std;

int farm[52][52];
int fcache[52][52];

void initFarm()
{
	for (int i = 0;i < 52;i++)
	{
		for (int j = 0;j < 52;j++)
		{
			farm[i][j] = 0;
			fcache[i][j] = 0;
		}
	}
}

int searchLand(int x, int y)
{
	int fup = farm[x - 1][y];
	int fdown = farm[x + 1][y];
	int fleft = farm[x][y - 1];
	int fright = farm[x][y + 1];

	int cup = fcache[x - 1][y];
	int cdown = fcache[x + 1][y];
	int cleft = fcache[x][y - 1];
	int cright = fcache[x][y + 1];

	fcache[x][y] = 1;

	if (fup + fdown + fleft + fright == 0)
		return 0;
	if (fup == cup && fdown == cdown && fleft == cleft && fright == cright)
		return 0;
	if (fup == 1 && cup == 0)
		searchLand(x - 1, y);
	if (fdown == 1 && cdown == 0)
		searchLand(x + 1, y);
	if (fleft == 1 && cleft == 0)
		searchLand(x, y - 1);
	if (fright == 1 && cright == 0)
		searchLand(x, y + 1);
	return 0;
}

int main(void)
{
	int T, M, N, K, X, Y;
	int ans;
	cin >> T;
	for (int i = 0;i < T;i++)
	{
		cin >> M >> N >> K;
		initFarm();
		ans = 0;
		for (int i = 0;i < K;i++)
		{
			cin >> X >> Y;
			farm[Y+1][X+1] = 1;
		}
		for (int i = 1;i <= N;i++)
		{
			for (int j = 1;j <= M;j++)
			{
				if (farm[i][j] == 1)
				{
					if (fcache[i][j]==0)
					{
						searchLand(i, j);
						ans += 1;
					}
					else
						continue;
				}
				else
					continue;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

작성한 모든 함수를 합치면 이렇게 된다.

 

III 느낀점

---

BFS 또는 DFS를 쓰는 이러한 형태의 문제는 사실 정말 흔히 마주칠 수 있었는데, 그 때마다 '어 이거 BFS/DFS네 나중에 따로 공부하고 해야지'하고 넘어가기 일쑤였다. 그러나 그 둘은 알고리즘의 기본이라고 할 수 있기에 더이상은 그러면 안될 것 같아서 풀기로 마음먹었다.

 

XY 좌표계와 2차원 배열 사이의 관계가 너무 헷갈렸다. 문제의 특성상 x와 y가 뒤집혀도 영역들이 분리되거나 합쳐지지 않기 때문에 답은 틀리지 않는다. 그래서 내가 맞게 했는지도 잘 모르겠다.

 

DFS를 재귀로 작성하면서, 재귀 함수는 피보나치로 배웠었기 때문에 당연히 return으로 재귀를 해야하는 줄 알았는데, return으로 재귀하니까 갈림길에서 한 방향으로 갔다가 다시 돌아오지 않고 그냥 끝나버리는 대참사를 두 눈으로 목격했다. 당연히 return을 써야하는 줄 알았는데, 함수 호출로 재귀를 해야한다는 점이 매우 골때렸다. 이번에 알게 되었으니 다행이다.

 

 

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 1012번 유기농 배추 C++

BOJ 1012번 유기농 배추 C++

백준 1012번 유기농 배추 C++