차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
이제 살짝 실버 구간과 골드 5 사이 구간의 백준 BFS문제들을 거의 진짜 똑같은 것 같다. 다른 문제들과 굉장히 유사하게 풀었고 어렵지 않은 문제였다!!
먼저 주의 해야할 점은 역시 역시 상하좌우의 내용들이 1인지 검사하고 queue에 넣어준 뒤 이동하여서 다시 검색하는 너비 우선 탐색이기 때문에 상하좌우의 정확한 인덱스가 들어갔는지 확인해야하였다. 또한 BFS가 한번 탐색될 때마다 배추 흰 지렁이의 마릿수를 추가해주는 것을 유의하면은 그렇게 어렵지 않았다. 범위도 그렇게 크지 않은 배열이였기 때문에 DFS를 사용하여도 쉽게 풀 수 있을 문제라고 생각된다.
void BFS(int v[50][50], int Ty, int Tx){
queue<pair<int, int>> q;
q.push({Tx, Ty});
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
visited[Ty][Tx] = true;
q.pop();
for(int i = 0;i < 4;i++){
int tempX = x + X[i];
int tempY = y + Y[i];
if(tempX >= 0 && tempY >= 0 && tempX < M && tempY < N && visited[tempY][tempX] == false && v[tempY][tempX] == 1){
q.push({tempX, tempY});
visited[tempY][tempX] = true;
}
}
}
}
함수 BFS만 간단하게 또 살펴보자면 배열과 탐색하는 위치의 인덱스를 매개변수로 받아서 이를 queue를 사용하여 상하좌우 중 탐색하지 않은 곳이 1의 값이라면 queue에 push해 주어 BFS를 완료해주었다.
아참 그리고 테스트케이스가 여러개가 올 수 있기 때문에 배열과 탐색여부를 확인하는 visited 배열을 초기화해주는 것을 잊지말아야한다!!
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T, M, N, K;
int X[4] = {0, 1, 0, -1};
int Y[4] = {-1, 0, 1, 0};
bool visited[50][50];
void BFS(int v[50][50], int Ty, int Tx){
queue<pair<int, int>> q;
q.push({Tx, Ty});
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
visited[Ty][Tx] = true;
q.pop();
for(int i = 0;i < 4;i++){
int tempX = x + X[i];
int tempY = y + Y[i];
if(tempX >= 0 && tempY >= 0 && tempX < M && tempY < N && visited[tempY][tempX] == false && v[tempY][tempX] == 1){
q.push({tempX, tempY});
visited[tempY][tempX] = true;
}
}
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int result = 0;
cin >> T;
for(int i = 0;i < T;i++){
cin >> M >> N >> K;
int v[50][50] = { 0 };
for(int i = 0;i < 50;i++){
for(int j = 0;j < 50;j++){
visited[i][j] = false;
}
}
for(int i = 0;i < K;i++){
int x, y;
cin >> x >> y;
v[y][x] = 1;
}
for(int i = 0;i < N;i++){
for(int j = 0;j < M;j++){
if(v[i][j] == 1 && visited[i][j] == false){
BFS(v, i, j);
result++;
}
}
}
cout << result << "\n";
result = 0;
}
return 0;
}
사실 알고리즘 풀고서 블로그에 글을 쓸지 말지 고민했었는데 이전에 풀었던 BFS문제와 굉장히 유사하고 내용만 달라서 그랬다,, 그래도 이번 것을 마지막으로 좀 다양한 내용이 섞여있는 그래프 탐색 문제를 풀어보도록 해볼려구 한다!! 이제 진짜 그래프 탐색이 익숙해지는 것 같당!! 열심히하자!!
화이팅~!!