DFS, BFS 문제입니다.
1은 배추가 심어져 있는 땅입니다.
배추가 심어진 땅에 지렁이를 한마리씩 두어야 하는데
인접한 땅에 배추가 심어져 있다면 한마리만 심어도 됩니다.
몇마리의 지렁이를 심어야지 찾는 문제입니다.
map을 전부 검사하면서 배추가 심어져 있으면 DFS를 통해서
인접한 곳들을 모두 0으로 해주고 count를 추가 해주었고
마지막까지 검사한 후 count를 출력하여 문제를 풀었습니다.
#include <iostream>
using namespace std;
int m, n, k;
int map[60][60];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };
void init()
{
for (int i = 0; i < 60; ++i) {
for (int j = 0; j < 60; ++j) {
map[i][j] = 0;
}
}
}
void DFS(int a, int b)
{
if (map[a][b] == 1) {
map[a][b] = 0;
for (int l = 0; l < 4; ++l) {
int x = moveX[l] + a;
int y = moveY[l] + b;
if (x >= 0 && y >= 0 && x < m && y < n) {
DFS(x, y);
}
}
}
}
int main(int argc, char *argv[])
{
int a, b;
int count;
int testcase;
cin >> testcase;
while (testcase--) {
init();
count = 0;
cin >> m >> n;
cin >> k;
for (int i = 0; i < k; ++i) {
cin >> a >> b;
map[a][b] = 1;
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (map[i][j] == 1) {
DFS(i, j);
++count;
}
}
}
cout << count << endl;
}
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 2555번 생일 출력하기 (0) | 2019.08.03 |
---|---|
[C++] 백준 1237번 정ㅋ벅ㅋ (0) | 2019.08.03 |
[C++] 백준 2667번 단지번호붙이기 (0) | 2019.07.30 |
[C++] 백준 11060번 점프 점프 (2) | 2019.07.18 |
[C++] 백준 1495번 기타리스트 (0) | 2019.07.16 |