[백준 알고리즘]/[C++]
1012번 유기농 배추 | DFS | Baekjoon BOJ 백준 1012 C++ 코드, 해설, 풀이
말하는펭귄
2021. 1. 29. 15:12
728x90
반응형
이번 포스팅은 백준 1012번 유기농 배추입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
기본 알고리즘
DFS 깊이 우선 탐색
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
//백준1012 유기농배추
#include <iostream>
using namespace std;
const int MAX = 51;
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;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = 0;
}
}
}
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() {
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] == 0) {
DFS(i, j);
cnt++;
}
}
}
cout << cnt << endl;
}
}
|
cs |
728x90
반응형