알고리즘 :: 백준 :: 1012 - 유기농 배추

 

 

 

 

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력:

• 테스트케이스 T (제한 따로 없음)
• 배추밭: 1 ≤ N, M ≤ 50, 가로M, 세로N 순으로 입력됨.
• 배추 개수 1 ≤ K ≤ 250 + 각 배추의 위치 (x좌표, y좌표 순으로 입력됨)
• 위치가 같은 배추는 없습니다.

출력: 필요한 최소 지렁이 개수 (Connected component 개수)

✏️ 문제풀이

서로 연결된 칸들의 집합, 그 집합이 몇 개 있는지를 구하는 connected component 구하기 문제입니다.

DFS, BFS 양쪽 모두로 풀 수 있습니다.

 

배추의 개수 및 위치를 입력받기 때문에

1. 배추 하나를 시작점으로 DFS 또는 BFS를 돌려 방문할 수 있는 모든 칸에 방문표시를 합니다. 이게 하나의 집합이 됩니다.
2. 배추밭을 더 순회합니다.
3. 아직 방문표시가 안 돼있는 배추를 발견했다면, 다시 그 위치를 시작점으로 DFS 또는 BFS를 돌립니다.
4. 이렇게 몇 번 DFS/BFS를 돌았는지 확인하면, 몇 개의 집합이 있는지 확인할 수 있다.

 

매 테스트케이스마다 방문표시를 초기화 하는 것은 꼭 잊지맙시다.

• STL 컨테이너에 대한 초기화 시, `fill()` 함수가 나은지 `memset()`이 나은지 햇갈릴 수 있습니다.
• 스스로와 약속만 하면 됩니다. `0` 또는 `-1`로 초기화를 한다면 `memset()`을 사용하세요.
• 그 이외의 수로 초기화를 한다면 `fill()` 또는 `fill_n()`을 사용하세요.
• 어차피 컴파일러도 알아서 잘 해석해주고, `fill()` 내부에서도 `memset()`을 사용하기 때문에 큰 고민 안 하셔도 됩니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

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

int T, N, M, K;
array<array<bool, 51>, 51> arr, visited;

inline bool isNotValid(int y, int x) {
	return (y < 0) || (y >= N) || (x < 0) || (x >= M);
}

void solve(int y, int x) {
	visited[y][x] = true;
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i], nx = x + dx[i];
		if (isNotValid(ny, nx) || !arr[ny][nx] || visited[ny][nx]) continue;
		solve(ny, nx);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> T;
	while (T--) {
		cin >> N >> M >> K;
		memset(&arr[0][0], 0, sizeof(arr));
		memset(&visited[0][0], 0, sizeof(visited)); 
		while (K--) {
			int y, x;
			cin >> y >> x;
			arr[y][x] = true;
		}
		int result = 0;
		for (int y = 0; y < N; ++y) {
			for (int x = 0; x < M; ++x) {
				if (arr[y][x] && !visited[y][x]) {
					solve(y, x);
					result++;
				}
			}
		}
		cout << result << '\n';
	}
}

 

🔗 코드 링크

🕧 결과