뚝딱뚝딱

개발자 톡방에서 GitHub Copilot chat에 대해 반응이 뜨겁길래 뭔가 하고 찾아봤다

대충 알아보니, vscode나 intelliJ 같은 개발환경에 설치하면, 이 Github Copilot chat이 내가 쓴 코드를 읽고 분석해서 더 최적화된 코드로 알려준다거나, 오류 등을 파악해서 바로 해결해주는 등의 마법사 같은 역할을 하는 것 같다.

지금까지 코드 상에 오류가 발생하면, 코드를 긁어서 CHAT GPT한테 물어보고, "오류를 수정해줘"라고 했을 것이다.

간단한 프로젝트면 그나마 나을지 모르지만, 큰 프로젝트나 코드의 길이, 여러 클래스들끼리 이리저리 얽혀있다면, 솔직히 그 많은 코드를 긁어서 완벽히 해결해달라고 하기엔 무리였다.

이제 CHAT GPT가 내장된 copilot chat이 내 프로젝트 코드들의 관계를 알아서 다 읽어보고 분석한 후, 오류가 발생한 부분에 대해서 척척 알려줄 것이다.

브라우저를 열었다 닫았다 할 귀찮음도 사라지고, 더이상 코드를 긁어 물어보지 않아도 되니 정말 좋은 서비스인것 같다.

다른 사람의 후기를 보니, 자신은 프론트엔드 개발자인데, copilot chat이 백엔드를 알아서 짜주고, 심지어는 db연결까지 다 해주었다고 한다. 풀스택이 가능해진 것이다.

이젠 백/프론트엔드 개발자라 하더라도 무리없이 보충해 풀스택으로 개발하는게 수월해질 것 같다.

다음은 공식 문서를 바탕으로 정리한 Github Copilot chat에 대한 부가 설명이다.

💡 GitHub Copilot Chat의 주요 기능!!

1. 코드 자동 완성

• 이 기능은 마치 나의 생각을 읽어내듯, 다음 코드 라인을 예측하고 제안해 주는 것이다.

2. 버그 수정

• 이 기능은 GitHub Copiolt Chat이 문제를 식별하고, 해결방안을 제시해 준다.
• 더이상 오류에 머리를 싸매지 않아도 된다!

💡 GitHub Copilot Chat의 장점!!

• 내 코드를 전체적으로 분석하고, 내 코딩 스타일에 맞추어서 코드를 제안해준다
• 설치과정이 몇분으로 간단하다
• 복잡한 코드, 어려운 알고리즘 문제 모두 copilot chat이 척척 도와줄것이다!!
• 코드를 작성하는 속도, 문제 해결 능력 향상 

다가오는 12월 중순 정식 출시 된다고 하네요!! 

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

💡 Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.

[입력]
첫째 줄에 정수 N, r, c가 주어진다.

[출력]
r행 c열을 몇 번째로 방문했는지 출력한다.

✅ 문제 풀이

• 분할과 정복 파트에 있는 문제이다.
• 하지만 흔히 푸는 방식인 재귀함수 호출을 이용한다면, 테스트 케이스는 통과할지 몰라도, 시간초과 또는 메모리 초과가 발생할 것이다.
• 일단 메모리 초과가 나는 이유는, 배열을 선언하고 저장하는 형태로 접근해서 일 것이다.
• 입력을 보면 우리는 최대 2^30 크기의 배열이 필요하게 되기 때문에, 기가 수준의 메모리가 필요해진다.
• 사실상, 주어진 입력을 통해 배열을 굳이 선언하지 않고도 단순히 카운트한 값만을 이용할 수 있으니, 배열은 필요없다
  -> 메모리초과 문제 해결
• 두번째는 시간 초과인데, 입력이 커지면, 굳이 필요없는 방문이 반복적으로 발생하게 된다. 즉 너무나 깊은 함수 호출로 인해 오히려 시간초과가 발생하는 것이다.
• 그럼 재귀호출 말고, 단순히 반복문으로 쉽게 카운트 하는 방법을 찾을 수 있다.

나는 다음과 같은 규칙을 찾아냈다.

1. 주어진 (r,c)의 번호는 이전에 이 영역에 도달하기 전에 크기가 1인 몇개의 영역을 지나왔는가와 동일하다.

• 예를 들어, 2*2크기의 배열이 있다고 할때, (1,1)에 도달 하기 전에는 (0,0),(0,1),(1,0)순으로 3개를 거친후 도달한다.
• 따라서 (1,1)의 번호는 3으로 매겨질 수 있는 것이다.

2. 주어진 (r,c)의 영역 범위와, 배열 크기에 따라 이전에 몇개를 거쳐오는지를 통채로 빠르게 계산할수 있다.

• 예를 들어 4*4 크기의 배열이 있다고 할때, (3,3)의 번호를 구하고 싶다고 하자.
• 이 위치는 배열을 4등분 했을 때, 방문 순서로 따지면 4번째 영역에 존재한다. 따라서 3번째 영역을 다 돌고 난 후의 값보다는 무조건 클 것이다.
• 그러므로 굳이 현재 (3,3)이 존재하는 4번째 영역을 제외하고는 일일이 탐색할 필요없이, 그 크기만큼 count에 더해주면 된다.
• 따라서 한 영역당 크기가 4이므로, 네번째 영역이라면, 4*3=12보다는 무조건 큰 번호를 가지게 된다.
• 이렇게 12를 count에 더해주고, 이제 네번째 영역을 하나의 배열이라 치고 위의 과정을 반복하면 된다.
• 이어서 설명하자면, 네번째 영역을 하나의 배열이라 치면 크기가 4인 배열이고, 여기서 (3,3)은 이 배열을 또 4등분 했을때 4번째 영역에 속하는 것이기 때문에, 한 영역당 크기가 1이므로, 1*3=3을 count에 더해주면 된다. 이제 (3,3)은 크기가 1인 배열이므로 더이상 쪼개지지 않고, 현재의 count 값인 15가 답이 되는 것이다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

void divide(int x, int y, int size, int &count, int &r, int&c) {
	while (size >= 1) {
		int set = pow(size / 2, 2);
		if (r < x + size / 2 && c < y + size / 2) {

		}
		else if (r < x + size / 2 && c >= y + size / 2 && c < y + size) {
			count += set;
			y += size / 2;
		}
		else if (r >= x + size / 2 && r < x + size && c < y + size / 2) {
			count += set * 2;
			x += size / 2;
		}
		else {
			count += set * 3;
			x += size / 2;
			y += size / 2;
		}
		size /= 2;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, r, c;

	cin >> N >> r >> c;

	int size = pow(2, N);//처음 행,열의 크기

	int count = 0;

	divide(0, 0, size, count, r, c);

	cout << count;

}

• 코드로 표현하자면 다음과 같이 접근했다.
• size를 배열의 한 변 길이로 두고, 그 배열에서 가장 처음 방문하는 곳을 x와 y로 두었다 .
• 배열의 한변 길이가 1이 될 때까지, 즉 계속해서 쪼개지는 배열이 하나의 요소가 될때까지 ,쪼개면서 count하도록 하였다.-> 분할과 정복
• set는 현재 배열에서 4등분 했을 때 각 영역의 크기를 저장한다.
• 이제 4개의 영역마다 서로 다른 로직을 따르도록 할것이다.
• 만약 (r,c)가 1번 영역에 속한다면 = 1번 영역은 배열 시작인 x,y각각에 size/2를 더한 것의 내부에 존재하는 영역이다.
  그렇다면 처음 방문인 거니까 x, y도 기준 그대로 이고, 이전 방문 내역이 없으므로 count하지 않아도 된다.
• 만약 (r,c)가 2번 영역에 속한다면 = 2번 영역은 배열 시작인 x에 size/2를 더한 것의 내부이면서, y는 size/2를 더한것의 이상이고 size를 더한 것보다는 작은 영역이다.
  그렇다면 이전에 1번 영역을 방문한 거니까, count에는 set만큼 더해주고, y의 기준을 size/2만큼 더해주어서 갱신해준다. 이 부분이 다음 단계에서는 첫 방문이 되도록 하기 위함이다.
• 만약 (r,c)가 3번 영역에 속한다면 = 3번 영역은 배열 시작인 x에 size/2를 더한것의 이상이면서 size를 더한것보다는 작은 영역이고, y에 size/2를 더한 것보다는 작은 영역이다.
  그렇다면 이전에 1번과 2번 영역을 방문한 거니까, count에는 set*2만큼 더해주고, x의 기준을 size/2만큼 더해주어서 갱신해준다. 이 부분이 다음 단계에서는 첫 방문이 되도록 하기 위함이다.
• 만약 (r,c)가 4번 영역에 속한다면 = 4번 영역은 배열 시작인 x에 size/2를 더한것의 이상이면서 size를 더한것보다는 작은 영역이고, y에 size/2를 더한 것의 이상이면서 size를 더한것보다는 작은 영역이다.
  그렇다면 이전에 1번과 2번과 3번 영역을 방문한 거니까, count에는 set*3만큼 더해주고, x의 기준을 size/2만큼, y의 기준을 size/2만큼 더해주어서 갱신해준다. 이 부분이 다음 단계에서는 첫 방문이 되도록 하기 위함이다.
• 한번씩 방문하고 나서는 size를 절반으로 나누어서 다음단계를 진행하도록 한다.
• 이를 size가 1이 될때까지 반복하면 된다.
• 그리고 while문을 빠져나오게 되면, 그때의 count값이 (r,c)의 번호가 된다. 

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

💡 수들의 합2

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

[입력]
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

[출력]
첫째 줄에 경우의 수를 출력한다.

수열에서 연속적인 값들의 합이 M과 같은 경우의 수를 구하는 문제이다.

✅ 문제 풀이

• 일단 누적합을 나타내는 sum에는 수열에서 첫번째 값을 넣어두고 시작한다.
• 실행시간 조건이 0.5초이기 때문에, for문에 의한 순회는 한번을 최대로 해야 한다.
• 그럼 부분 합을 어떻게 구할 수 있을까?
• 두 포인터를 이용해서, 시작 지점과 끝 지점을 가리키도록 한다.
• 그것을 각각 s와 e로 하고, 수열의 인덱스를 가리키도록 한다.
• 처음에는 s와 e를 0으로 시작한다. 따라서 sum도 수열의 첫번째 값만을 담고 있어야 한다.
• 그렇게 해서 s<=e를 만족하는 한 계속 경우의 수를 찾아갈 것이다.
• if문을 통해 현재의 sum값과 M을 비교한다.
• 만약 sum이 M보다 작으면, 더 더해주어야 하기때문에 e를 하나 늘리고, 현재 e가 가리키는 값을 sum에 더해준다.
  이때 주의할 점은, 하나 늘어난 e가 N을 넘지 않아야 한다는 것이다. N을 넘지 않았을 경우에만 e가 가리키는 값을 sum에 더해주면 된다.=>유효성을 확인하는 부분이다.
• 만약 sum이 M과 같다면, 하나의 경우가 되는 것이므로, 경우의 수를 카운트하는 answer를 하나 늘려준다.
  그리고 수열의 모든 값은 자연수이기 때문에, s를 늘리면 값을 줄고, e를 늘리면 값이 늘어나게 되는 건 분명하다. 따라서 이 경우에는 s와 e를 둘다 하나씩 늘리도록 한다.
• 만약 sum이 M보다 크다면, 빼주어야 하기때문에, sum에서 현재 s가 가리키는 값을 빼준다.
  그리고 여기서 주의할 점이 있다.
  만약 s가 e와 동일했었다면 다음 값을 sum에 넣어주어야 하기 때문에, s와 e를 둘다늘리고, 이 둘이 가리키는 값을 sum에 넣어주도록 한다.
  s와 e가 동일하지 않았다면 s를 하나 늘려주면 된다.
• 그리고 for문을 다 순회한 후에는 answer를 출력해주면 된다. 

☑ 코드 전문

#include<iostream>

using namespace std;

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

	int N, M;
	cin >> N >> M;

	int arr[10000];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	int sum = arr[0];
	int answer = 0;
	for (int s = 0, e = 0; s <= e;) {
		if (sum < M) {
			e++;
			if (e < N) sum += arr[e];
			else break;
		}
		if (sum == M) {
			answer++;
			sum -= arr[s];
			s++;
			e++;
			if (e < N) sum += arr[e];
			else break;
		}
		if (sum > M) {
			sum -= arr[s];
			if (s == e && e < N - 1) {
				s++;
				e++;
				sum += arr[e];
			}
			else {
				s++;
			}
		}
	}

	cout << answer;
}

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

💡 트리

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

[입력]
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

[출력]
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

✅ 문제 풀이

• 각 노드에 대한 자식 노드를 저장하기 위해서, vector 형태의 크기가 50인 배열 tree을 생성해주었다.
  vector<int> tree[50]
• 입력으로 N이 1부터 50까지 들어올 수 있기 때문에, 노드는 0~49임을 고려한 것이다.
• 차례대로 입력받을 때 0번 노드부터 부모를 입력받는다.
• 따라서 -1인 경우를 제외하고, 나머지 경우에 대해서는 입력받은 값을 p라고 했을 때, tree[p]에다가 해당 노드를 저장해준다.
  vector형태니까, push_back(해당 노드) 해주면 된다.
• 그럼 모든 노드에 대해서 바로 아래 자식 노드 리스트를 가지게 된다. 당연히, 자식이 없는 노드의 벡터는 비어있을 것이다.
• 그리고 삭제된 노드인지, 리프노드인지를 구별하기 위해 bool타입의 배열 leaf를 생성해서 false로 초기화 해주었다.
• 삭제할 노드를 입력받고, 해당 노드를 기준으로 dfs함수를 호출한다.
• dfs 함수에서는 다음과 같이 동작한다.
  입력 : tree, 삭제할 노드 node, leaf
  로직
  - 삭제할 노드의 자식 노드들을 순회한다. 즉 tree[node]를 순회한다.
  - 이 때 자식 노드를 num에 저장해두고, 자식의 자식들을 순회하기 위해 dfs를 호출하여 삭제할 노드로 num을 넘겨준다.
  -그리고 해당 노드에 대해 모두 순회했으면, tree[node]를 clear하여 모두 삭제해주고, 이는 삭제된 노드이므로 leaf[node]를 true로 변경해준다.
• 입력한 삭제 노드에 대해 위 로직을 따르고 나면, 이제 입력 값만을 부모에서 삭제해주면 된다.
• 부모를 찾기위해서 2중 for문을 통해 입력받은 값을 자식으로 갖는 노드가 있는지 순회하고, 일치하다면 해당 부모 노드의 배열에서 삭제하도록 한다. 그리고 순회를 즉시 멈춘다.
• 이제 삭제할 노드를 기점으로 모두 삭제되었으므로, tree배열을 순회하면서 leaf가 false이고(=삭제되지 않은노드), tree[i]의 size가 0인 노드를 카운트 하여 출력한다.  

☑ 코드 전문

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

void dfs(vector<int> tree[], int node, bool leaf[]) {
	for (int i = 0; i < tree[node].size(); i++) {
		int num = tree[node][i];
		dfs(tree, num, leaf);
	}
	tree[node].clear();
	leaf[node] = true;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<int> tree[50];
	bool leaf[50] = {false};//false->true 개수만 세기
	for (int i = 0; i < N; i++) {
		int p;
		cin >> p;
		if (p == -1) continue;
		else {
			tree[p].push_back(i);
		}
	}

	int node;
	cin >> node;

	dfs(tree, node, leaf);

	bool br=false;
	for (int i = 0; i < N; i++) {
		for (auto it = tree[i].begin(); it != tree[i].end(); it++) {
			if (*it==node) {
				tree[i].erase(it);
				br = true;
				break;
			}
		}
		if (br) break;
	}

	int answer = 0;

	for (int i = 0; i < N; i++) {
		if (!leaf[i]&&tree[i].size() == 0) answer++;
	}

	cout << answer;
    
    return 0;
}

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

💡 문자열

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.
두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.
1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.
이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

[입력]
첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

[출력]
A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

✅ 문제 풀이

문자열을 다루는 문제이다.

문제를 가만 보면, A의 앞에 문자를 추가하거나 뒤에 문자를 추가하거나에 초점을 맞출 시에는 복잡해진다.

어차피 채울 수 있는 문자열은 B와 동일한 문자열을 채우면 되기 때문에, 상관하지 않도록 한다.

A문자열 그 자체만을 보고, B문자열과 비교하는 것이다.

B문자열의 앞에서부터 A문자열 크키만큼 비교하는데, 그 차이가 가장 적을 때가 A와 B의 차이를 최소로 하는 것이다.

예를 들어서 B에 A문자열이 완전히 포함된다면 어떨까?

그럼 A문자열이 포함되는 부분을 제외하고만 A에 앞 뒤로 B와 동일하게 문자를 붙혀준다면, 두 문자열은 동일한게 되는 것이므로 차이는 0이 된다.

따라서 A가 B 중에서 가장 적게 차이나는 값을 구하면 된다.

그러기 위해 B에서 A를 뺀 값+1 만큼 for문을 돌면서 A와 B를 비교하는데, 이때 B를 그냥 비교하는게 아니라, A의 길이만큼 일정부분 잘라서 비교하도록 하였다. 이때는 string의 substr함수를 사용하였다.

이런식으로 A를 B의 앞 부터 밀어가면서 비교해보는 것이다.

☑ 코드 전문

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

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

	string a, b;
	cin >> a >> b;
	
	int cnt = 50;

	for (int i = 0; i < b.length() - a.length() + 1; i++) {
		string str = b.substr(i, a.length());
		int now = 0;
		for (int j = 0; j < a.length(); j++) {
			if (a[j] != str[j]) now++;
		}
		cnt = min(cnt, now);
	}

	cout << cnt;
}

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

💡 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
1100000000
0100000000
0000100000
0000100000
0011000111
0000100111

[입력]
입력의 첫 줄에는 테스트 케이스의 개수 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이면서 동서남북으로 인접한 1이 존재할 때 한 영역이 되기 때문에, 한 영역안에서는 모든 1이 서로 인접한 1이 존재한다는 것이다. 따라서 어떤 값이 1이면 연쇄적으로 인접한 값을 마주할 때 까지 탐색하여 하나의 영역으로 구할 수 있다. 따라서 이 문제는 DFS로 해결할 수 있다.

1. 먼저 매 테스트 케이스마다 배열에 값을 저장한다. 입력으로 받는 k개의 배추 위치에 대해 1로 저장하고 나머지는 0으로 저장하면 된다.
2. 배열의 크기만큼 순회하는데, 값이 1이면 첫번 째 영역에 대한 시작이므로, count를 1 증가시킨 후, dfs 함수를 호출한다.
3. dfs 함수에서는 현재 값이 1인 위치와, arr를 &로 넘겨준다. &로 넘겨주는 이유는 방문한 칸에 대해서는 arr의 값을 수정해주기 위해서이다.
4. dfs 함수가 호출되면, 현재 인자로 받은 위치의 값을 0으로 바꾸어준다. 그 이유는 방문했음을 나타내기 위함과, 나중에 main의 for문에서 재방문 하지 않게 하기 위함이다.=> 이 문제의 핵심이다.
5. 그리고 현재의 위치를 기준으로 동서남북 방향에 있는 값이 1인지 확인한다.
6. 1이라면 같은 영역이므로, 그 칸을 기준으로 dfs 함수를 호출하도록 한다.
7. 따라서 위의 과정을 반복하다 보면 동일한 영역에 해당하는 값들이 1에서 모두 0으로 바뀌게 되고, main문에서 해당 영역에 해대 시작했던 탐색이 끝나게 되어 하나의 영역을 탐색할 수 있게 되는 것이다.
8. 위 과정을 거친 후 최종 count 값이 바로 영역의 개수가 되고, 필요한 지렁이의 개수가 된다.

☑ 코드 전문

#include<iostream>
#include<vector>

using namespace std;

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

void dfs(int x, int y, vector<vector<int>> &arr) {
	arr[x][y] = 0;

	for (int n = 0; n < 4; n++) {
		int r = x + dx[n];
		int c = y + dy[n];
		if (r>=0&&r<arr.size()&&c>=0&&c<arr[0].size()&&arr[r][c] == 1) {
			dfs(r, c, arr);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;//테스트 케이스 개수
	cin >> T;

	for (int i = 0; i < T; i++) {
		int M, N, K;//가로, 세로, 총 배추 개수
		cin >> M >> N >> K;
		vector<vector<int>> arr(N, vector<int>(M, 0));//배추밭

		for (int j = 0; j < K; j++) {
			int x, y;
			cin >> y >> x;
			arr[x][y] = 1;
		}//배추 심기

		int count = 0;//배추흰지렁이의 개수

		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (arr[j][k] == 1) {
					count++;
					dfs(j, k, arr);
				}
			}
		}

		cout << count << "\n";

	}
}