BOJ 1012 유기농 배추

📎Problem Link

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

1012번: 유기농 배추

📋 문제 정리

• 배추흰지렁이는 상하좌우로 움직일 수 있어 배추 하나에만 있어도 상하좌우에 배추가 심어져있으면 이동 가능!
• 0은 배추가 심어져 있지 않은 땅, 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)를 입력

 

📌 예제1

• TC1
  

  1	1
  	1
  				1
  				1
  		1	1			1	1	1
  				1		1	1	1
  						1	1	1

  위의 표를 보면 5개의 배추흰지렁이가 필요함을 알 수 있다.
• TC2
  

  					1

  위의 표를 보면 5개의 배추흰지렁이가 필요함을 알 수 있다.

 

📌 예제2

• TC1
  

  				1
  1	1	1	1	1

  위의 표를 보면 2개의 배추흰지렁이가 필요함을 알 수 있다.

---

💻 Code

 

#include <iostream>
#include <vector>
#include<cstring>
using namespace std;
#define WIDTH_MAX 50
#define HEIGHT_MAX 50
int move_x[4] = { 0, 0, 1, -1 };
int move_y[4] = { 1, -1, 0, 0 };

class Farming
{
public:
	int Width, Height, Count; //field 사이즈와 배추 심어진 개수, 지렁이에 대한 정보
	int field[HEIGHT_MAX][WIDTH_MAX]; //밭 크기 임의 지정
	bool visited[HEIGHT_MAX][WIDTH_MAX]; //밭 방문한 경로 체크
	void dfs(int y, int x) {
		for (int i = 0; i < 4; i++) {
			int next_x = x + move_x[i];
			int next_y = y + move_y[i];

			if ((next_x < 0) || (next_x >= Width) || (next_y < 0) || (next_y >= Height))
				continue;

			if (field[next_y][next_x]==1 && !visited[next_y][next_x])
			{
				visited[next_y][next_x] = true;
				dfs(next_y, next_x);
			}
			else visited[next_y][next_x] = true;
		}
	}
};

1년 전의 나는 이 문제를 풀 때 모든 변수를 전역 변수로 선언했다. 모든 함수에서 변수들을 쉽게 사용하기 위함이었다. 하지만 그 때도 그렇고 지금도 그렇고, 암만 봐도 모든 변수를 전역으로 선언하는게 코드가 깔끔하지 않다는 기분이 들었다. 그래서 비록 public 선언이긴 하지만 class를 생성하여 그 안에 모든 변수를 때려박았다. private으로 선언할까 했지만 그러기엔 변수를 사용할 때 private 변수를 불러올 함수를 따로 생성해야한다는 생각에 그냥 public으로 했다.

 

밭 크기의 경우는 가로, 세로 값이 얼마가 들어올지 모르기 때문에 제일 MAX 값으로 임의 지정했다. visited의 경우 최대한 작은 크기의 변수를 사용하고자 bool 타입을 사용했다. 

 

Depth First Search인 dfs 함수답게, y좌표를 먼저 움직일 수 있게 move_x와 move_y 변수를 설정하여 for문을 통해 탐색이 가능하게 했다. 변경한 좌표 값이 밭 범위 내에 유효하지 않은 값일 때는 continue;를 통해 새로운 좌표 변경을 할 수 있게 했고, 유효한 경우 변경한 좌표에 배추가 있고 방문한 적이 없을 때에 dfs함수를 call할 수 있도록 했다.

 

int main()
{
	Farming Hanna;
	int earthworm, testCase;
	cin >> testCase; //testCase 개수 입력

	for (int t = 0; t < testCase; t++)
	{
		earthworm = 0; // 지렁이 개수 초기화
		memset(Hanna.visited, false, sizeof(Hanna.visited)); //방문 체크 배열 초기화
		memset(Hanna.field, 0, sizeof(Hanna.field)); //field 초기화
		cin >> Hanna.Width >> Hanna.Height >> Hanna.Count; //밭에 대한 정보 입력
		for (int i = 0; i < Hanna.Count; i++) //배추가 심어진 좌표 입력
		{
			int x, y;
			cin >> x >> y;
			Hanna.field[y][x] = 1;
		}

		for (int i = 0; i < Hanna.Height; i++) { //밭을 돌며 dfs로 밭 심어진 영역 개수 count
			for (int j = 0; j < Hanna.Width; j++) {
				if ((Hanna.visited[i][j] == false) && (Hanna.field[i][j] == 1)) { //아직 확인 안한 영역 && 그 영역에 배추가 있을 때
					Hanna.visited[i][j] = true;
					Hanna.dfs(i, j);
					earthworm++; //배추가 모여있는 영역 개수 count
				}
			}
		}
		cout << earthworm << endl;
	}
}

main 문의 큰 특이점은 없다. 굳이 하나를 뽑자면 새로운 테스트 케이스에 대한 field 배열과 visited 배열을 memset으로 초기화한다는 점,,,?? 그리고 배추가 뭉쳐있는 구역마다 배추흰지렁이가 하나만 있으면 되기 때문에 배추가 모여있는 구역 하나하나를 다 돌고 나올 때마다 earthworm을 증가시켜 최소로 필요한 배추흰지렁이를 구했다.

 

 

---

위의 코드로 돌린 후 1년 전과 비교해보니 메모리면에서 아주 큰 변화가 있었다. 도대체 1년 전에 코드를 어떻게 짰길래 메모리를 저렇게 크게 썼을까 싶으면서도 메모리면에서 더 효율적인 코드를 짰다는 사실에 뿌듯함을 느꼈다!