https://www.acmicpc.net/problem/1012
//C++
#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535
using namespace std;
typedef long long ll;
int m, n, k, cnt;
int arr[54][54];
int visited[54][54];
int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
queue<pair<int, int> > q;
void dfs(int i, int j)
{
visited[i][j] = 1;
for (int k = 0; k < 4; k++)
{
int next_i = i + dir[k][0];
int next_j = j + dir[k][1];
//mark2
if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < m && visited[next_i][next_j] == 0 && arr[next_i][next_j] == 1)
{
dfs(next_i, next_j);
}
}
return;
}
int main()
{
F_I;
int tc;
cin >> tc;
while (tc--)
{
memset(arr, 0, sizeof(arr));
memset(visited, 0, sizeof(visited));
cnt = 0;
cin >> m >> n >> k;
for (int i = 0; i < k; i++)
{
int a, b;
cin >> a >> b;
arr[b][a] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] == 0 && arr[i][j] == 1) //mark1
{
dfs(i, j);
++cnt;
}
}
}
cout << cnt << '\n';
}
}
> mark1 : 반복문을 차례차례 돌면서, 배추가 심어져 있는데(arr[i][j]==1) 아직 방문 하지 않은 땅이라면(visited[i][j]==0)
그 땅을 기준으로 dfs로 탐색을 시작한다. 여기에서 탐색이 끝났다는 이야기는, (마지막 땅의 상하좌우에 있는 땅 중에서 mark2를 만족하는 땅이 없다는 의미이므로), 그 범위까지 지렁이 1마리가 필요한 것이다. 그러므로 탐색이 끝난 이후, 지렁이의 마리 수를 체크하는 cnt 변수를 1 만큼 증가시킨다.
> mark2 : mark1의 조건을 만족한 어떠한 땅이 있을 때, 그 땅에서 다음으로 나아갈 수 있는 땅의 후보군은 상하좌우 밖에 없다. 이때, 이 3가지의 조건을 만족해야 진정으로 나아갈 수 있다.
1. 밭 범위 내에 있는가? (밭의 범위를 벗어나지 않아야 한다!)
2. 아직 방문하지 않은 땅인가?
3. 밭에 배추가 심어져 있는가?
'Problem Solving > 백준' 카테고리의 다른 글
[백준] 17413번 : 단어 뒤집기 2 (0) | 2020.08.27 |
---|---|
[백준] 7569번 : 토마토 (0) | 2020.08.22 |
[백준] 12865번 : 평범한 배낭 (0) | 2020.08.12 |
[백준] 11052번 : 카드 구매하기 (0) | 2020.08.10 |
[백준] 16929번 : Two Dots (0) | 2020.08.04 |