<๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ์ ์ฌ๊ฐํ ๋ชจ์์ ์ง๋๊ฐ ์๋ค. 1์ ์ง์ด ์๋ ๊ณณ์, 0์ ์ง์ด ์๋ ๊ณณ์ ๋ํ๋ธ๋ค. ์ฒ ์๋ ์ด ์ง๋๋ฅผ ๊ฐ์ง๊ณ ์ฐ๊ฒฐ๋ ์ง์ ๋ชจ์์ธ ๋จ์ง๋ฅผ ์ ์ํ๊ณ , ๋จ์ง์ ๋ฒํธ๋ฅผ ๋ถ์ด๋ ค ํ๋ค. ์ฌ๊ธฐ์ ์ฐ๊ฒฐ๋์๋ค๋ ๊ฒ์ ์ด๋ค ์ง์ด ์ข์ฐ, ํน์ ์๋์๋ก ๋ค๋ฅธ ์ง์ด ์๋ ๊ฒฝ์ฐ๋ฅผ ๋งํ๋ค. ๋๊ฐ์ ์์ ์ง์ด ์๋ ๊ฒฝ์ฐ๋ ์ฐ๊ฒฐ๋ ๊ฒ์ด ์๋๋ค. <๊ทธ๋ฆผ 2>๋ <๊ทธ๋ฆผ 1>์ ๋จ์ง๋ณ๋ก ๋ฒํธ๋ฅผ ๋ถ์ธ ๊ฒ์ด๋ค. ์ง๋๋ฅผ ์ ๋ ฅํ์ฌ ๋จ์ง์๋ฅผ ์ถ๋ ฅํ๊ณ , ๊ฐ ๋จ์ง์ ์ํ๋ ์ง์ ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ฒซ ๋ฒ์งธ ์ค์๋ ์ง๋์ ํฌ๊ธฐ N(์ ์ฌ๊ฐํ์ด๋ฏ๋ก ๊ฐ๋ก์ ์ธ๋ก์ ํฌ๊ธฐ๋ ๊ฐ์ผ๋ฉฐ 5โคNโค25)์ด ์ ๋ ฅ๋๊ณ , ๊ทธ ๋ค์ N์ค์๋ ๊ฐ๊ฐ N๊ฐ์ ์๋ฃ(0ํน์ 1)๊ฐ ์ ๋ ฅ๋๋ค.
์ฒซ ๋ฒ์งธ ์ค์๋ ์ด ๋จ์ง์๋ฅผ ์ถ๋ ฅํ์์ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ ๋จ์ง๋ด ์ง์ ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ์์ค.
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
3
7
8
9
์ด ๋ฌธ์ ๋ ์ธ์ ํ ํ๋ ฌ์ ๊ฐ์ ํ๋จํ์ฌ ๊ณ์ ํ์ํด ๋๊ฐ๋ ๋ฌธ์ ์ด๊ธฐ ๋๋ฌธ์, DFS๋ BFS๋ฅผ ์ฌ์ฉํ๋ฉด ๋ ๊ฒ์ด๋ผ๋ ์๊ฐ์ด ๋ค์๋ค.
๋ ์ค, ๋๋ DFS๋ฐฉ์์ผ๋ก ์ ๊ทผํด ๋ณด์๋ค.
๋จ์ง๋ฅผ ํ์ํด ๋๊ฐ๋ ๊ณผ์ ์
๋ง์ฝ, ๋ฐฉ๋ฌธํ์ง ์์ ์ง์ ๋ฐ๊ฒฌํ๋ค๋ฉด, ํด๋น ์ง์ ์ํ์ข์ฐ๋ฅผ ์ดํ ํ,
์ธ์ ํ ์ง์ด ์๋ค๋ฉด, ํด๋น ์ง์ผ๋ก ๋ฐฉ๋ฌธ ํ DFS๋ฅผ ํธ์ถํ๋ ๋ฐฉ์์ผ๋ก ์ค๊ณ๋ฅผ ํ์๋ค.
์ฃผ์ํด์ผ ํ ์ ์ ์ํ์ข์ฐ๋ฅผ ์ดํ ๋, ์ง๋ ๋ฒ์ ๋ฐ์ ํ์ํ๋ฉด Out Of Bound ์ค๋ฅ๊ฐ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์, ํ์ํ ์ธ๋ฑ์ค๊ฐ ์ง๋ ๋ฒ์ ์์ด๋ผ๋ ์กฐ๊ฑด์ ๊ณ ๋ คํด์ผ ํ๋ค.
ํ์ฌ ์ง์ด๋ ์ธ์ ํ๊ณ , ๋ฐฉ๋ฌธํ์ง ์์ ์ง์ ๋ฐฉ๋ฌธํด DFS ํธ์ถ์ ํ ๋, count
๋ณ์๋ฅผ ์ฆ๊ฐ์์ผ ๋จ์ง ์๋ฅผ ์ฆ๊ฐ์์ผ ์ฃผ๊ณ , ๋จ์ง ํ์์ด ๋๋ฌ์ ๋ ์ด๋ฅผ ๋ฐํํด ๋ฐฐ์ด์ ์ ์ฅํ๋๋ก ๊ตฌํํ์๋ค.
import java.util.ArrayList;
import java.util.Scanner;
import static java.util.Collections.sort;
public class Main {
static int[][] map; // ์ง๋
static boolean[][] visited; // ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ๋ด๊ณ ์๋ ๋ฐฐ์ด
static int size; // ์ง๋์ ํฌ๊ธฐ
static int count;
static int[][] see = {{-1, 0},{1, 0}, {0, -1}, {0, 1}}; // ์ํ์ข์ฐ
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
size = sc.nextInt();
sc.nextLine();
map = new int[size][size]; // ์ง๋ ์์ฑ
visited = new boolean[size][size]; // ๋ฐฉ๋ฌธ ์ฌ๋ถ
ArrayList<Integer> result = new ArrayList<>();
// ๋ฐฐ์ด ์
๋ ฅ๋ฐ๊ธฐ
for (int i = 0; i < size; i++) {
String[] input = sc.nextLine().split("");
for (int j = 0; j < size; j++) {
map[i][j] = Integer.parseInt(input[j]);
}
}
// ๋จ์ง ์ฐพ๊ธฐ
for (int i = 0; i < size; i++){
for (int j = 0; j < size; j++) {
// ์ง์ด ์กด์ฌํ๊ณ ๋ฐฉ๋ฌธํ์ง ์์์ ๊ฒฝ์ฐ
if (map[i][j] == 1 && !visited[i][j]) {
count = 0;
dfs(i, j); // dfs ํธ์ถ
result.add(count); // ๋จ์ง ์ ์ ์ฅ
}
}
}
System.out.println(result.size());
sort(result);
for (int integer : result) {
System.out.println(integer);
}
}
// DFS
static void dfs(int x, int y) {
count++; // ๋จ์ง ์ ์ฆ๊ฐ
visited[x][y] = true;
// ์ํ์ข์ฐ ํ์
for (int i = 0; i < see.length; i++) {
// ์ํ์ข์ฐ ์ด๋ํ ์ขํ
int newX = x + see[i][0];
int newY = y + see[i][1];
// ์ด๋ํ ์ขํ๊ฐ map ์์ ์๊ณ , ์ด๋ํ ์ขํ์ ์ง์ด ์๊ณ , ๋ฐฉ๋ฌธํ์ง ์์์ ๋
if (newX >= 0 && newX < size && newY >= 0 && newY < size && map[newX][newY] == 1 && !visited[newX][newY]) {
dfs(newX, newY);
}
}
}
}
DFS๋ฅผ ๋ฌธ์ ์ ์ ์ฉํ๋ ๊ฒ ์์ง์ ์ด๋ ต๊ธด ํ์ง๋ง, ์ ์ฌํ ๋ฌธ์ ๋ฅผ ๋ ํ์ด๋ณด๋ฉฐ ์ ์์ ํด์ผ๊ฒ ๋ค๐
ํ๊ณ๋ฅผ ๋ฐ์ด๋์ด๐ฅ๐ฅ