백준 1926 - 그림 [C++, 파이썬]

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

1926번: 그림

---

풀이 과정

배열에서 연결 요소의 개수와 연결 요소의 가장 큰 크기를 구하는 문제이다.

 

연결 요소의 개수와 크기를 구하려면 DFS 혹은 BFS로 모든 배열을 탐색하면 된다.

---

소스 코드

C++

#include <bits/stdc++.h>
using namespace std;

bool vis[501][501];
bool board[501][501];

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

int bfs(int y, int x) {
    if (vis[y][x] || board[y][x] == 0) {
        return 0;
    }
    cou++;
    int width = 1;

    vis[y][x] = true;
    queue<pair<int, int>> Q;
    Q.push(make_pair(y, x));


    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();

        for (int i = 0 ; i < 4; i++) {
            int nx = cur.second + dx[i];
            int ny = cur.first + dy[i];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (vis[ny][nx] || board[ny][nx] != 1) continue;
            vis[ny][nx] = true;
            width++;
            Q.push(make_pair(ny, nx));
        }
    }

    return width;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> answer_list;
    int board_number;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board_number;
            board[i][j] = board_number;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            answer_list.push_back(bfs(i, j));
        }
    }

    cout << cou << '\n';

    cout << *max_element(answer_list.begin(), answer_list.end());

    return 0;
}

 

파이썬

import collections
import sys

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
gaesu = 0


def bfs(start_y, start_x, board):
    if vis[start_y][start_x] or not board[start_y][start_x]:
        return 0
    global gaesu
    gaesu += 1
    width = 1
    vis[start_y][start_x] = 1
    queue = collections.deque()
    queue.append([start_y, start_x])

    while queue:
        y, x = queue.popleft()
        for cur in range(4):
            nx = x + dx[cur]
            ny = y + dy[cur]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if not board[ny][nx] or vis[ny][nx]:
                continue
            vis[ny][nx] = 1
            width += 1
            queue.append([ny, nx])

    return width


n, m = map(int, sys.stdin.readline().split())
vis = [[0 for _ in range(m)] for _ in range(n)]
board = []
answer = []
for i in range(n):
    board.append(list(map(int, sys.stdin.readline().split())))

for i in range(n):
    for j in range(m):
        answer.append(bfs(i, j, board))

print(gaesu)
print(max(answer))