[백준/Baekjoon] 1012번 유기농 배추 (C++)

문제

---

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

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 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)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

 

출력

---

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

 

정답코드

​

#include <iostream>
#include <string.h>
using namespace std;
int M, N, K; // 가로, 세로, 위치개수
int field[50][50] = { 0 };
int visited[50][50] = { 0 };
int move_x[4] = {1, -1, 0, 0}; 
int move_y[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
	for (int t = 0; t < 4; t++) {
    	// 검사할 값에서 인접한 값으로 변경!
		int xx = move_x[t] + x;
		int yy = move_y[t] + y;
        
		if (xx < 0 || xx >= M || yy < 0 || yy >= N) continue; // 필드를 벗어났을 경우
		if (field[xx][yy] && !visited[xx][yy]) {
			visited[xx][yy]++;
			dfs(xx, yy);
		}
	}
}
int main() {
	int T; // 테스트 케이스 개수
	
	int x, y;
	int answer = 0;
	cin >> T;
	for (int test_cast = 0; test_cast < T; test_cast++) {
		cin >> M >> N >> K;
		answer = 0;
        // 배열 초기화
		memset(visited, 0, sizeof(visited));
		memset(field, 0, sizeof(field));
		
        // 필드 만들기
		for (int i = 0; i < K; i++) {
			cin >> x >> y;
			field[x][y] = 1;
		}

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j] && field[i][j]) { // 방문하지 않았고, 필드에 배추가 심어져있음
					answer++;
					visited[i][j]++;
					dfs(i, j);
				}
			}
		}
		cout << answer << '\n';
	}


}

 

문제해석

문제의 표로 나타나있는 필드에서  1로 표시된 부분을 하나의 영역으로 보고 이 부분의 수를 카운트합니다.

 

저는 이 문제를 깊이우선탐색으로 풀이하였습니다.

먼저 입력값에 해당하는 위치의 값을 1로 변경합니다.

 

다음으로 모든 필드의 영역을 탐색합니다.

 

그리고 1로 표시된 부분을 만나게되면 그 부분을 시작으로 인접해있는 1로 표시된 부분을 탐색합니다.

이때 해당영역은 방문한 적이 없어야 합니다.

방문한 곳은 visited라는 배열에 0이 아닌 다른값으로 변경하여 표시합니다.

필요한 애벌레의 값을 저장할 answer변수의 값을 증가시킵니다.

그 위치를 시작으로 깊이우선탐색을 시작합니다.

조금 다른점은 인접한 부분을 확인해야하기 때문에 move_x와 move_y라는 배열이 필요합니다.

move_x[0]과 move_y[0]의 값이 각각 1과 0일경우에는 x축만 1 증가시키기 때문에 오른쪽으로 한칸 이동한 부분을 확인하는 것입니다.

다른것도 마찬가지로 4개의 값을 저장한 배열을 통해 상하좌우를 검사합니다.

 

xx라는 변수에는 내가 검사를 할 위치의 값 + 상하좌우중 하나 선택한 값 을 저장합니다. 

yy도 마찬가지로 동작합니다. 

이러한 방식을 통해 검사할 위치의 인접한 값을 검사할 수 있습니다.

 

첫번째 조건문은 검사할 값이 필드를 벗어났을 경우에 해당하는 조건입니다. 이때는 continue를 통해 반복문을 벗어납니다.

그리고 동일하게 검사할 영역을 방문하지 않았고, 검사할 영역의 값이 1일경우 

재귀를 통해 동일하게 검사합니다.

 

이과정 반복!!.....

 

여기서 메인에 있는 memset은 이 문제가 T라는 값을 받아 여러번 검사 할 수 있게 해야하기 때문에 새로운 케이스에서는 visited와 field 배열이 초기화 되어야 합니다.

이때 memset를 통해 간편하게 비울 수 있습니다.

memset(해당 배열,어떤값으로 초기화?,배열의 크기)

여기서 배열의 크기는 보통 sizeof를 이용하여 적는 것 같습니당..

그리고! 몰랐던 점이였는데.. 두번째 매개변수가 0이면 이 0은 int형이 아닌 string으로 초기화가 됩니다.

따라서 #include <string.h>를 선언하지 않으면 안됩니당..!!

그래서 한번 틀렸었습니다..ㅎㅎㅎ