[BOJ 21938] 영상처리 c++

난이도: Silver 2
번호: 21938
생성일: February 27, 2023 3:15 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

21938번: 영상처리

C++

BFS

메모리	시간
6924 kb	400 ms

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int map[1002][1002];
bool visit[1002][1002];

const int dX[] = {0, 0, -1, 1};
const int dY[] = {-1, 1, 0, 0};

int N, M, T, res;

void BFS(int i, int j)
{
    queue<pair<int, int>> Q;
    Q.push({i, j});
    visit[i][j] = true;

    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for (int k = 0; k < 4; k++)
        {
            int x = cur.first + dX[k];
            int y = cur.second + dY[k];

            if (map[x][y] < T || visit[x][y])
                continue;

            Q.push({x, y});
            visit[x][y] = true;
        }
    }
}

int main(void)
{
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            map[i][j] = (a + b + c) / 3;
        }

    cin >> T;  
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            if (map[i][j] >= T && !visit[i][j])
            {
                BFS(i, j);
                res++;
            }

    cout << res;
    return (0);
}

C++

DFS

메모리	시간
17624 kb	400 ms

#include <iostream>
#include <vector>

using namespace std;

int map[1002][1002];
bool visit[1002][1002];

const int dX[] = {0, 0, -1, 1};
const int dY[] = {-1, 1, 0, 0};

int N, M, T, res;

void DFS(int i, int j)
{
    for (int k = 0; k < 4; k++)
    {
        int x = i + dX[k];
        int y = j + dY[k];

        if (map[x][y] < T || visit[x][y])
            continue;

        visit[x][y] = true;
        DFS(x, y);
    }
}

int main(void)
{
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            map[i][j] = (a + b + c) / 3;
        }

    cin >> T;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            if (map[i][j] >= T && !visit[i][j])
            {
                visit[i][j] = true;
                DFS(i, j);
                res++;
            }

    cout << res;
    return (0);
}