- toc {:toc}
문제
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다.농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 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)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
출력
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
출처:https://www.acmicpc.net/problem/1012
풀이
다 풀었는데…. board판은 초기화해놓고 vis판의 초기화를 생각못했다.
BFS 풀이 그대로 풀이하면 된다. 결국 변화하는 것은 조건식 뿐이기 때문에 조건식만 주의해서 확인하면 된다.
2022-07-31 풀이
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int m, n, k;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--){
int board[55][55] = {}; // 테스트 케이스가 많기 때문에
int vis[55][55] = {}; // 꼭 초기화를 해줘야 함.
cin >> m >> n >> k;
while(k--){ // 배추가 있는 곳 표시
int x, y;
cin >> x >> y;
board[y][x] = 1;
}
/*
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cout << board[i][j];
}
cout << endl;
}
*/
queue<pair<int, int>> q;
int ans = 0; // BFS 돌리기
for(int row=0; row<n; row++){
for(int col=0; col<m; col++){
if(vis[row][col] == 0 && board[row][col] == 1){
vis[row][col] = 1;
q.push({row, col});
ans++;
}
while(!q.empty()){
auto cur = q.front(); q.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] != 0 || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
cout << ans << endl;
}
}2023-09-06 풀이
새롭게 다시 풀어봤는데, 로직의 변화는 없다.
1로 이루어진 영역이 몇 개 인지 구하는 문제이기 때문에 1인 부분을 처음 들어갈 때 영역 체크를 해주고 BFS를 이용해 연결된 영역을 -1로 없애준다. 다음과 같은 방식으로 전부 찾으면 몇 마리의 배추흰지렁이가 필요한지 알 수 있다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int T, M, N, K;
queue<pair<int, int>> q;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while(T--){
int board[55][55] = {0,};
cin >> M >> N >> K;
for(int i = 0; i < K; i++){
int x, y;
cin >> x >> y;
board[x][y] = 1;
}
int res = 0;
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
if(board[i][j] == 0 || board[i][j] == -1) continue;
q.push({i, j});
board[i][j] = -1;
res++;
while(!q.empty()){
auto cur = q.front(); q.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
if(board[nx][ny] == 0 || board[nx][ny] == -1) continue;
q.push({nx, ny});
board[nx][ny] = -1;
}
}
}
}
cout << res << '\n';
}
return 0;
}