유기농 배추

---

문제

왼쪽 오른쪽 위 아래를 인접으로 보고 지렁이가 최소 몇개가 필요한지를 구하는 문제이다.

풀이

먼저 지렁이가 필요한 위치에 놓고, 그 인접한 부분을 dfs나 bfs로 계속해서 탐색해 나가면 된다.

---

코드 작성

간단한 풀이지만, 코드를 간결하고 이쁘게 작성하기 위한 몇가지 팁들이 들어간다.

x축 y축 표현

가로 M, 세로 N이다. 우리가 수학문제를 풀때 쓰는 x,y좌표는 x가 가로, y가 세로이므로
M : x, N : y에 해당한다.
하지만 2차원 배열을 생각해보면 arr[i][j]에서 i는 세로, j가 가로에 해당한다.
따라서 배열에 값을 입력하거나 추출할때는 i : y, j : x에 해당한다. 즉 arr[y][x]를 사용해야 한다.

M, x, j는 가로를 표현하는 방법, N, y, i는 세로를 표현하는방법

상하좌우 등 이동을 나타내는 배열

dy[], dx[]를 사용해 변위량을 미리 저장해놓으면 간단하게 위치변화를 표현할 수 있다.

for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"

#define MAX 50+1
int t, m, n, k;
int map[MAX][MAX];
int visited[MAX][MAX];
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };

void reset() {
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			map[i][j] = 0;
			visited[i][j] = false;
		}
	}

}

void dfs(int y,int x) {
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx<0 || nx>=m || ny <0 || ny>=n)
		{
			continue;
		}

		if (map[ny][nx]==1 && visited[ny][nx]==0)
		{
			dfs(ny, nx);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> t;
	while (t--)
	{
		cin >> m >> n >> k;

		reset();

		while (k--)
		{
			int x, y;
			cin >> x >> y;
			map[y][x] = 1;
		}
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j]==1 && visited[i][j]== false)
				{
					dfs(i, j); // 심기
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}

}

참고