[백준 1926] 그림 (C++/Python)

C++)

#include <iostream>
#include <queue>
#define MAX_NUM 502
using namespace std;

int arr[MAX_NUM][MAX_NUM];
bool visited[MAX_NUM][MAX_NUM];
queue<pair<int, int>> q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int bfs(int m, int n) {
	int count = 0;

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

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			
			if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;

			if (arr[nx][ny] == 1 && !visited[nx][ny]) {
				q.push({ nx, ny });
				visited[nx][ny] = true;
			}
		}
	}

	// 그림의 넓이 return
	return count;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	// 1. 입력받는다.
	int m, n;
	cin >> m >> n;

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

	int total = 0;
	int answer = 0;

	// 2. (0,0)부터 색칠 유무를 검사한다.
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {

			// 3. 아직 방문 안했으며 색칠이 되어있다.
			if (!visited[i][j] && arr[i][j] == 1) {
				
				// 4. 방문 처리하고 넓이를 계산한다.
				q.push({ i,j });
				visited[i][j] = true;
				int temp = bfs(m, n);
				answer = (answer < temp) ? temp : answer;
				total++;
			}
		}
	}

	cout << total << "\n" << answer;

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()

n, m = map(int, read().rstrip().split())
arr = [ [0] * m for _ in range(n)]
visited = [ [False] * m for _ in range(n)]

for i in range(n):
    arr[i] = list(map(int, read().rstrip().split()))

tot = 0
ans = 0

def bfs():
    cnt = 0

    while q:
        x, y = q.popleft()
        cnt += 1

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if visited[nx][ny]:
                continue

            if arr[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx,ny))
                
    return cnt

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and not visited[i][j]:
            visited[i][j] = True
            q.append((i,j))
            tot += 1

            ans = max(ans, bfs())
            

print(tot)
print(ans)