PS
[C++] 1012 : 유기농 배추
왕방토
2021. 1. 30. 00:59
728x90
실버Ⅱ
#include <iostream>
using namespace std;
int map[50][50] = { 0, };
int m, n;
void dfs(int x, int y) {
if (map[x][y] == 0 || x < 0 || x >= m || y < 0 || y >= n) return;
map[x][y] = 0;
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
}
int main() {
int t, k, x, y;
scanf("%d", &t);
int cnt;
//테스트 케이스 동안
for (int i = 0; i < t; i++) {
cnt = 0;
//테스트 마다 m n k 새로 받기
scanf("%d%d%d", &m, &n, &k);
//밭의 k개의 배추 위치들 입력받기
for (int j = 0; j < k; j++) {
scanf("%d%d", &x, &y);
map[x][y] = 1;
}
//map에서 1이면(배추면) dfs 돌기
for (int a = 0; a < m; a++) {
for (int b = 0; b < n; b++) {
if (map[a][b] == 1) {
dfs(a, b);
cnt++;
}
}
}
printf("%d\n", cnt);
}
}
DFS 응용문제로 풀었지만 BFS나 DFS 아무거나 이용해도 되는 문제다!
(BFS 배우면 BFS로도 바로 풀어보기)
따로 check[50][50] 배열을 만들지 않고
dfs를 탐색하는 기준이 map의 값이 1인 것이므로
map의 값을 0을 바꿔서 자동으로 더 이상 dfs가 들어가지 않도록 함
(원래 dfs :
map(here) = 1 -> dfs (here)
check(here) = 1인가? 아니면 next 노드ㄱㄱ
이 문제에서의 응용 :
map(here) = 1 -> dfs (here), map (here)= 0
이 되므로 자연스럽게 차단!)
x y가 거꾸로 되어있어서 좀 헷갈리긴 하는데.. 별로 상관없다 어차피
x - 1 x + 1 y - 1 y + 1 다 보니까