알고리즘/백준
백준_1012 : 유기농 배추 - C++
맏리믓
2023. 5. 10. 23:53
문제

알고리즘
- 이 문제는 그래프 탐색의 가장 기초적인 형태이다.
- 방문여부를 기록 하는 visited 배열과 배추 위치를 기록하는 배열을 관리한다.
- 이때 지렁이가 갈 수 있는 곳을 visited 로 기록 하면서 지렁이의 수를 카운트 해 주면 된다.
코드
- 그래프 탐색을 위해 x, y 의 이동 방향을 1, 0, -1 로 조절 한다.
- arr 를 반복하며 배추가 심어져 있고 visited 하지 않은 곳을 dfs 로 넘겨 지렁이를 보낸 후 상, 하, 좌, 우를 visited 처리 하면 된다.
#include <iostream>
#include <string.h>
using namespace std;
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
int M,N,K;
int arr[50][50];
int visited[50][50];
void dfs(int y, int x){
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= N || nx < 0 || nx >= M){
continue;
}
if(arr[ny][nx] && !visited[ny][nx]){
visited[ny][nx] += 1;
dfs(ny,nx);
}
}
}
int main(){
int T, x, y;
cin >> T;
for(int testCase = 0; testCase < T; testCase++){
cin >> M >> N >> K;
memset(arr, 0, sizeof(arr));
memset(visited, 0, sizeof(visited));
int ans = 0;
for(int i = 0; i < K; i++){
cin >> x >> y;
arr[y][x] = 1;
}
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
if(arr[i][j] && !visited[i][j]){
ans += 1;
visited[i][j] += 1;
dfs(i, j);
}
cout << ans << endl;
}
}