인프런 커뮤니티 질문&답변

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

int main() {
    cin >> n >> m >> k;

    vector<vector<int>> Map(n + 1, vector<int>(m + 1, 0));
    vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, false));
    vector<pair<int, int>> flooded;

    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        Map[x][y] = 1;
        flooded.push_back({ x, y });
    }

    int max_size = 0;
    for (auto& start : flooded) {
        if (visited[start.first][start.second]) continue;

        int size = 0;
        queue<pair<int, int>> Q;
        Q.push(start);
        visited[start.first][start.second] = true;

        while (!Q.empty()) {
            size++;
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && Map[nx][ny] == 1 && !visited[nx][ny]) {
                    Q.push({ nx, ny });
                    visited[nx][ny] = true;
                }
            }
        }

        max_size = max(max_size, size);
    }

    cout << max_size << endl;

    return 0;
}

DFS가 아닌 BFS 사용해도 문제는 풀립니다.

공부중이라 어느게 더 효율적인지는 모르겠습니다만, 혹시 BFS로 접근하실 분들 참고하라고 올려봅니다~