[백준] 1012번: 유기농 배추

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

1012번: 유기농 배추

DFS로 푼 문제

일단 문제에 나온 것처럼 배추의 위치를 저장하는 2차원 배열을 만들고

(인덱스 범위가 넘어가는 것을 방지하기 위해 상하좌우로 1칸씩 여유칸 만들었음)

 

배열을 한칸 한칸 탐색해가며 배추가 있는 경우 DFS를 하면 된다.

음.. BFS로도 할 수 있을 것 같은데..?

 

컴포넌트 하나 탐색이 끝날 때마다 cnt를 1씩 증가시키고 최종적으로 cnt 출력하면 끝

 

처음 풀었던 건 visited 배열을 따로 만들어줬는데 두번째 코드에서는 matrix값을 0으로 만들어가며 구현했다.

 

그 외에.. 방향 탐색하는건 dir 배열을 따로 만들어주면 편하다?

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool>> matrix;
vector<vector<bool>> visited;

int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

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

	for (int i = 0; i < 4; i++) {
		int x2 = x + dir[i][0];
		int y2 = y + dir[i][1];
		if (matrix[x2][y2] && !visited[x2][y2]) {
			dfs(x2, y2);
		}
	}
}

int main() {
	int T;
	cin >> T;
	
	while (T--) {
		int m, n, k;
		cin >> m >> n >> k;
		matrix.assign(m + 2, vector<bool>(n + 2, 0));
		visited.assign(m + 2, vector<bool>(n + 2, 0));

		for (int i = 0; i < k; i++) {
			int x, y;
			cin >> x >> y;
			x++;
			y++;
			matrix[x][y] = 1;
		}

		int cnt = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (!matrix[i][j]) continue;
				if (visited[i][j]) continue;

				dfs(i, j);

				cnt++;
			}
		}

		cout << cnt << "\n";

		matrix.clear();
		visited.clear();
	}
}

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool>> matrix;

int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void dfs(int x, int y) {
	matrix[x][y] = 0;

	for (int i = 0; i < 4; i++) {
		int x2 = x + dir[i][0];
		int y2 = y + dir[i][1];
		if (matrix[x2][y2]) {
			dfs(x2, y2);
		}
	}
}

int main() {
	int T;
	cin >> T;
	
	while (T--) {
		int m, n, k;
		cin >> m >> n >> k;
		matrix.assign(m + 2, vector<bool>(n + 2, 0));

		for (int i = 0; i < k; i++) {
			int x, y;
			cin >> x >> y;
			x++;
			y++;
			matrix[x][y] = 1;
		}

		int cnt = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (!matrix[i][j]) continue;

				dfs(i, j);

				cnt++;
			}
		}

		cout << cnt << "\n";

		matrix.clear();
	}
}