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)'백준 2 > 그래프' 카테고리의 다른 글
| [백준 7562] 나이트의 이동 (Python) (0) | 2023.06.28 |
|---|---|
| [백준 5014] 스타트링크 (C++/Python) (0) | 2023.04.05 |
| [백준 2610] 회의준비 (Java) (0) | 2020.12.24 |
| [백준 13168] 내일로 여행 (Java) (0) | 2020.12.24 |
| [백준 1920] 수 찾기 (Java) (0) | 2020.12.15 |