알고리즘/백준

백준_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;
    }
}