[백준 1012번] 유기농 배추

백준 1012번 유기농 배추

이 문제는 백준 2667번 단지번호붙이기와 거의 같은 문제이다.

단지번호붙이기와 다른점은 단지마다 넓이를 구해야하고, 유기농 배추는 단지의 갯수만 구하면 되는 문제이다.

1. BFS를 이용한 풀이

#include<cstdio>
#include<queue>
 
using namespace std;
 
queue<pair<int, int>> q;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int map[55][55] = { 0 };
 
int main()
{
    int T;
    int m, n, k;
    int x, y;
    int ans;
    scanf("%d", &T);
    for (; T--;)
    {
        ans = 0;
        scanf("%d %d %d", &m, &n, &k);
        for (int i = 0; i < k; i++)
        {
            scanf("%d %d", &x, &y);
            map[y + 1][x + 1] = 1;
        }
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (map[i][j])
                {
                    ans++;
                    map[i][j] = 0;
                    q.push(make_pair(i, j));
                    while (!q.empty())
                    {
                        pair<int, int> now = q.front(); q.pop();
 
                        for (int k = 0; k < 4; k++)
                        {
                            if (map[now.first + dy[k]][now.second + dx[k]])
                            {
                                map[now.first + dy[k]][now.second + dx[k]] = 0;
                                q.push(make_pair(now.first + dy[k], now.second + dx[k]));
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

2. DFS(재귀)를 이용한 풀이

#include<cstdio>
 
int map[55][55] = { 0 };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
void dfs(int i, int j)
{
    map[i][j] = 0;
    for (int k = 0; k < 4; k++)
    {
        if (map[i + dy[k]][j + dx[k]]) {
            map[i + dy[k]][j + dx[k]] = 0;
            dfs(i + dy[k], j + dx[k]);
        }
    }
}
 
int main()
{
    int T;
    int n, m, k;
    int x, y;
    int ans;
    scanf("%d", &T);
    for (; T--;)
    {
        ans = 0;
        scanf("%d %d %d", &m, &n, &k);
        for (int i = 0; i < k; i++)
        {
            scanf("%d %d", &x, &y);
            map[y + 1][x + 1] = 1;
        }
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (map[i][j])
                {
                    map[i][j] = 0;
                    ans++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

3. DFS(stl stack)를 이용한 풀이

#include<cstdio>
#include<stack>
#include<algorithm>
 
using namespace std;
 
stack<pair<int, int>> st;
 
int map[55][55] = { 0 };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int main()
{
    int T;
    int n, m, k;
    int x, y;
    int ans;
    scanf("%d", &T);
    for (; T--;)
    {
        ans = 0;
        scanf("%d %d %d", &m, &n, &k);
        for (int i = 0; i < k; i++)
        {
            scanf("%d %d", &x, &y);
            map[y + 1][x + 1] = 1;
        }
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (map[i][j])
                {
                    map[i][j] = 0;
                    ans++;
                    st.push(make_pair(i, j));
 
                    while (!st.empty())
                    {
                        pair<int, int> now = st.top(); st.pop();
 
                        for (int k = 0; k < 4; k++)
                        {
                            if (map[now.first + dy[k]][now.second + dx[k]])
                            {
                                map[now.first + dy[k]][now.second + dx[k]] = 0;
                                st.push(make_pair(now.first + dy[k], now.second + dx[k]));
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}