https://www.acmicpc.net/problem/1012
문제 분석
배추를 보호하기 위해 인접해있는 배추 무리마다 배추흰지렁이를 배치하기 위해서 배추흰지렁이가 얼마나 필요한지를 구하는 문제이다. 배추는 상하좌우 네 방향으로 붙어있는 경우에 인접한 것이다. 인접한 배추 무리가 몇 개인지 구하면 된다. 너비우선탐색(BFS)를 통해 문제를 풀 수 있다.
코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 50
int map[MAX][MAX];
queue<pair<int, int>> q;
int n, m, k;
bool visited[MAX][MAX];
int ans;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void reset(){
for(int i=0; i<50; i++){
for(int j=0; j<50; j++){
map[i][j] = 0;
visited[i][j] = false;
}
}
ans = 0;
}
void bfs(int x, int y){
visited[x][y] = true;
q.push(make_pair(x, y));
while(!q.empty()){
x = q.front().first;
y = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx>=0 && ny>=0 && nx<n && ny<m){
if(map[nx][ny]==1 && !visited[nx][ny]){
visited[nx][ny] = true;
q.push(make_pair(nx, ny));
}
}
}
}
}
int main(){
int t;
cin>>t;
for(int p=0; p<t; p++){
reset();
cin>>m>>n>>k;
for(int i=0; i<k; i++){
int a, b;
cin>>a>>b;
map[b][a] = 1;
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(map[i][j]==1 && !visited[i][j]){
bfs(i, j);
ans++;
}
}
}
cout<<ans<<"\n";
}
return 0;
}
문제 풀이
- 테스트케이스의 개수 t를 입력받고 반복문으로 t번동안 아래 과정을 반복한다.
- reset함수로 배추밭을 입력받을 map과 방문했었는지 여부를 저장할 visited를 초기화한다.
- 배추밭의 크기인 m, n과 배추의 개수 k를 입력받고 배추의 위치들을 입력받아 map의 해당 위치를 1로 설정한다.
- 배추밭에서 배추가 심어진 곳을 찾아야 하므로 이중 반복문을 통해 모든 위치를 보도록 하고 배추가 있고 방분한 적이 없을 때에는 현재 위치를 인자로 bfs함수를 실행한 후 답이 될 ans값을 1 증가시킨다.
- bfs함수에서는 이미 방문한 곳을 다시 방문하지 않도록 하기 위해서 visited를 조정한다. 인자 x, y는 현재 위치이므로 visited[x][y]를 true로 설정하고 x, y를 pair로 만들어 큐 q에 push한다. 그 후 q가 비지 않는 동안, 즉 더 이상 조건에 충족하는 위치가 없을 때까지, q의 첫 번째 값들을 저장하고 pop한 후, 반복문을 통해 상하좌우 네 방향을 모두 방문하여 조건을 만족하면 해당 위치의 visited를 true로 설정하고 q에 push하도록 한다.
- 이러면 ans는 bfs가 실행될 때마다, 즉 배추 무리를 찾을 때마다 증가하게 되므로 ans를 출력하면 된다.
'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/JAVA] 20304 비밀번호 제작 (0) | 2022.08.13 |
---|---|
[백준/C++] 1303 전쟁 - 전투 (0) | 2022.08.12 |
[백준/C++] 9328번 열쇠 (0) | 2022.08.08 |
[백준/Python] 11286번 절댓값 힙 (0) | 2022.08.07 |
[백준 / Python] 17298 - 오큰수 (0) | 2022.08.07 |