[백준] 1012 유기농 배추

문제 설명

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

배추가 심어져있는 곳은 1, 배추가 심어져 있지 않은 곳은 0으로 표시가 되어있는 땅이 있다

배추흰지렁이는 배추를 해충으로부터 보호하고, 인접해있는 다른 배추로도 이동할 수 있다

이따 필요한 총 지렁이의 개수 구하기

 

문제 풀이법

배추흰지렁이의 개수를 구한다는 뜻은, 배추가 이어져서 심어져있는 곳의 개수를 구하라는 말과 같다

 

모든 지점을 방문하는 문제이기에 bfs, dfs 모두 사용하여 문제를 풀 수 있다

 

땅을 나타내는 배열 arr, 방문했는지 나타내는 배열 visited이 필요하다

모든 배열을 0으로 초기화 한 후, 배추가 심어져 있는 위치의 개수 k만큼 위치를 받아서 해당 위치에 배추가 있다는 표시로 arr[y][x] = 1로 체크해준다 

 

이후 (0,0)부터 (n, m)번동안 검사를 하면서 배추가 있는 곳인 arr[y][x] == 1 이면서 visited[y][x] == 0인 곳에만 bfs/dfs를 돈다

총 bfs/dfs가 돈 횟수를 센 뒤 출력한다

 

위의 동작을 테스트 케이스 t번동안 반복한다

 

소스 코드

bfs

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int t, n, m, k;
int arr[51][51];
int visited[51][51];

int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };


void bfs(int y, int x)
{
    visited[y][x] = 1;
    
    queue<pair<int, int>> q;
    q.push({y, x});
    
    while (!q.empty())
    {
        int yy = q.front().first;
        int xx = q.front().second;
        
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            
            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            if (arr[ny][nx] == 0 || visited[ny][nx] == 1)
                continue;
                
            q.push({ny, nx});
            visited[ny][nx] = 1;
        }
    }
}

int main()
{
    cin >> t;
    
    while (t--)
    {
        cin >> m >> n >> k;
    
        for (int i = 0; i < n; i++)
        {
            fill(arr[i], arr[i] + m, 0);
            fill(visited[i], visited[i] + m, 0);
        }

        for (int i = 0; i < k; i++)
        {
            int x, y;
            cin >> x >> y;
            arr[y][x] = 1;
        }
    
        int cnt = 0;
    
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (arr[i][j] == 1 && visited[i][j] == 0)
                {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

 

dfs

#include <iostream>

using namespace std;

int t, n, m, k;
int arr[51][51];
int visited[51][51];

int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };


void dfs(int y, int x)
{
    if (visited[y][x] == 1)
        return ;
        
    visited[y][x] = 1;
    

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
            
        if (ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if (arr[ny][nx] == 0 || visited[ny][nx] == 1)
            continue;
        dfs(ny, nx);
    }
}

int main()
{
    cin >> t;
    
    while (t--)
    {
        cin >> m >> n >> k;
    
        for (int i = 0; i < n; i++)
        {
            fill(arr[i], arr[i] + m, 0);
            fill(visited[i], visited[i] + m, 0);
        }

        for (int i = 0; i < k; i++)
        {
            int x, y;
            cin >> x >> y;
            arr[y][x] = 1;
        }
    
        int cnt = 0;
    
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (arr[i][j] == 1 && visited[i][j] == 0)
                {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}