import java.io.*;
import java.util.*;
public class complex_number_2667 {
static int n;
static int[][] graph;
static int number;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int count;
static Queue<int[]> queue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
graph = new int[n][n];
number = 1;
count = 0;
queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
String row = br.readLine();
for (int j = 0; j < n; j++) {
graph[i][j] = Character.getNumericValue(row.charAt(j));
}
}
int[] countArr = new int[n * n];
int islandCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1) {
number++;
count = bfs(number, i, j);
countArr[islandCount++] = count;
}
}
}
System.out.println(number-1);
int[] nonZeroCountArr = Arrays.stream(countArr).filter(x -> x != 0).toArray();
Arrays.sort(nonZeroCountArr);
for (int i = 0; i < islandCount; i++) {
System.out.println(nonZeroCountArr[i]);
}
}
static int bfs(int number, int sy, int sx) {
queue.clear();
queue.add(new int[]{sy, sx});
graph[sy][sx] = number;
count = 1;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int y = curr[0];
int x = curr[1];
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if ( 0 <= ny && ny < n && 0 <= nx && nx < n && graph[ny][nx] == 1) {
queue.add(new int[]{ny, nx});
graph[ny][nx] = number;
count++;
}
}
}
return count;
}
}
해당 코드는 섬의 개수와 각 섬의 크기를 구하는 BFS(Breadth-First Search) 알고리즘을 사용한 문제 해결 코드입니다. 자료구조로는 2차원 배열 graph
, 정수형 배열 dx
와 dy
, 정수형 변수 n
, number
, count
, islandCount
, 그리고 큐 queue
를 사용합니다.
graph
: 2차원 배열로 섬의 맵을 나타냅니다. graph[i][j]
는 i번째 행과 j번째 열의 위치에 있는 육지(1) 또는 바다(0)를 나타냅니다.
dx
와 dy
: 상하좌우로 이동하기 위한 배열입니다. dx
는 열의 이동을, dy
는 행의 이동을 나타냅니다. 즉, (dy[d], dx[d])
는 상하좌우 각 방향으로 이동하기 위한 좌표 변화를 나타냅니다.
n
: 섬의 맵의 크기를 나타내는 변수입니다.
number
: 섬을 식별하기 위한 번호입니다. 섬을 발견할 때마다 번호를 증가시켜 사용합니다.
count
: 섬의 크기를 저장하는 변수입니다.
islandCount
: 발견된 섬의 개수를 저장하는 변수입니다.
queue
: BFS 탐색을 위한 큐입니다. 큐에는 섬의 좌표를 저장합니다.
해당 코드의 로직은 다음과 같습니다.
입력값으로 섬의 맵 크기 n
을 받습니다.
2차원 배열 graph
를 섬의 맵으로 초기화합니다.
countArr
배열을 섬의 개수만큼 생성합니다.
islandCount
를 0으로 초기화합니다.
이중 반복문을 사용하여 맵의 모든 좌표를 순회합니다.
현재 좌표가 육지(1)인 경우, number
를 증가시키고 해당 좌표를 기준으로 BFS 탐색을 수행하여 섬의 크기 count
를 구합니다.
countArr
배열에 count
를 저장하고, islandCount
를 증가시킵니다.
섬의 번호(number-1)
와 섬의 크기를 출력합니다.
countArr
배열에서 0이 아닌 값들을 추출하여 nonZeroCountArr
배열에 저장합니다.
nonZeroCountArr
배열을 오름차순으로 정렬합니다.
islandCount
만큼 반복하면서 nonZeroCountArr
배열을 출력합니다.
따라서 해당 코드는 주어진 섬의 맵에서 섬의 개수와 각 섬의 크기를 구하는 BFS 알고리즘을 사용하여 문제를 해결하는 코드입니다.
const readline = require("readline");
input = [];
let n;
let graph;
let number = 1;
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
let count;
let queue;
const bfs = (number, sy, sx) => {
queue = [];
queue.push([sy, sx]);
graph[sy][sx] = number;
count = 1;
while (queue.length > 0) {
const [y, x] = queue.shift();
for (let d = 0; d < 4; d++) {
const ny = y + dy[d];
const nx = x + dx[d];
if (0 <= ny && ny < n && 0 <= nx && nx < n && graph[ny][nx] === 1) {
queue.push([ny, nx]);
graph[ny][nx] = number;
count++;
}
}
}
return count;
};
readline
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
n = parseInt(input[0]);
graph = new Array(n);
for (let i = 1; i < n + 1; i++) {
graph[i - 1] = input[i].split("").map(Number);
}
const countArr = [];
let islandCount = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (graph[i][j] === 1) {
number++;
count = bfs(number, i, j);
countArr.push(count);
islandCount++;
}
}
}
console.log(number - 1);
countArr.sort((a, b) => a - b);
for (let i = 0; i < islandCount; i++) {
console.log(countArr[i]);
}
process.exit();
});
from collections import deque
def bfs(graph, number, sy, sx):
global n, count
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append((sy, sx))
while (queue):
y, x = queue.popleft()
graph[y][x] = number
count += 1
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if ( 0 <= ny < n and 0 <= nx < n and graph[ny][nx] == 1):
queue.append((ny, nx))
graph[ny][nx] = number
return count
n = int(input())
graph = []
number = 1
count_lst = []
count = 0
for _ in range(n):
graph.append(list(map(int, input())))
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
number += 1
count_lst.append(bfs(graph, number, i, j))
count = 0
print(number-1)
count_lst.sort()
for _ in range(len(count_lst)): print(count_lst[_])