반응형
https://www.acmicpc.net/problem/1012
💡 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
1100000000
0100000000
0000100000
0000100000
0011000111
0000100111
[입력]
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
[출력]
필요한 배추흰지렁이의 개수를 구하라.
✅ 문제 풀이
값이 1이면서 동서남북으로 인접한 1이 존재할 때 한 영역이 되기 때문에, 한 영역안에서는 모든 1이 서로 인접한 1이 존재한다는 것이다. 따라서 어떤 값이 1이면 연쇄적으로 인접한 값을 마주할 때 까지 탐색하여 하나의 영역으로 구할 수 있다. 따라서 이 문제는 DFS로 해결할 수 있다.
- 먼저 매 테스트 케이스마다 배열에 값을 저장한다. 입력으로 받는 k개의 배추 위치에 대해 1로 저장하고 나머지는 0으로 저장하면 된다.
- 배열의 크기만큼 순회하는데, 값이 1이면 첫번 째 영역에 대한 시작이므로, count를 1 증가시킨 후, dfs 함수를 호출한다.
- dfs 함수에서는 현재 값이 1인 위치와, arr를 &로 넘겨준다. &로 넘겨주는 이유는 방문한 칸에 대해서는 arr의 값을 수정해주기 위해서이다.
- dfs 함수가 호출되면, 현재 인자로 받은 위치의 값을 0으로 바꾸어준다. 그 이유는 방문했음을 나타내기 위함과, 나중에 main의 for문에서 재방문 하지 않게 하기 위함이다.=> 이 문제의 핵심이다.
- 그리고 현재의 위치를 기준으로 동서남북 방향에 있는 값이 1인지 확인한다.
- 1이라면 같은 영역이므로, 그 칸을 기준으로 dfs 함수를 호출하도록 한다.
- 따라서 위의 과정을 반복하다 보면 동일한 영역에 해당하는 값들이 1에서 모두 0으로 바뀌게 되고, main문에서 해당 영역에 해대 시작했던 탐색이 끝나게 되어 하나의 영역을 탐색할 수 있게 되는 것이다.
- 위 과정을 거친 후 최종 count 값이 바로 영역의 개수가 되고, 필요한 지렁이의 개수가 된다.
☑ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void dfs(int x, int y, vector<vector<int>> &arr) {
arr[x][y] = 0;
for (int n = 0; n < 4; n++) {
int r = x + dx[n];
int c = y + dy[n];
if (r>=0&&r<arr.size()&&c>=0&&c<arr[0].size()&&arr[r][c] == 1) {
dfs(r, c, arr);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;//테스트 케이스 개수
cin >> T;
for (int i = 0; i < T; i++) {
int M, N, K;//가로, 세로, 총 배추 개수
cin >> M >> N >> K;
vector<vector<int>> arr(N, vector<int>(M, 0));//배추밭
for (int j = 0; j < K; j++) {
int x, y;
cin >> y >> x;
arr[x][y] = 1;
}//배추 심기
int count = 0;//배추흰지렁이의 개수
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
if (arr[j][k] == 1) {
count++;
dfs(j, k, arr);
}
}
}
cout << count << "\n";
}
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 1068번 C++ "트리" 풀이 / 그래프 탐색, DFS 알고리즘 (1) | 2023.11.26 |
---|---|
[백준] 1120번 C++ "문자열" 풀이 / 브루트포스 알고리즘 (0) | 2023.11.23 |
[백준] 1005번 C++ "ACM Craft" 풀이 / 위상정렬, 큐, 그래프 알고리즘 (2) | 2023.11.22 |
[백준] 1026번 C++ "보물" 풀이 / 그리디 알고리즘 (1) | 2023.11.21 |
[백준] 1010번 C++ "다리 놓기" 풀이 / 조합 (0) | 2023.11.20 |