<๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ์ ์ฌ๊ฐํ ๋ชจ์์ ์ง๋๊ฐ ์๋ค. 1์ ์ง์ด ์๋ ๊ณณ์, 0์ ์ง์ด ์๋ ๊ณณ์ ๋ํ๋ธ๋ค. ์ฒ ์๋ ์ด ์ง๋๋ฅผ ๊ฐ์ง๊ณ ์ฐ๊ฒฐ๋ ์ง์ ๋ชจ์์ธ ๋จ์ง๋ฅผ ์ ์ํ๊ณ , ๋จ์ง์ ๋ฒํธ๋ฅผ ๋ถ์ด๋ ค ํ๋ค. ์ฌ๊ธฐ์ ์ฐ๊ฒฐ๋์๋ค๋ ๊ฒ์ ์ด๋ค ์ง์ด ์ข์ฐ, ํน์ ์๋์๋ก ๋ค๋ฅธ ์ง์ด ์๋ ๊ฒฝ์ฐ๋ฅผ ๋งํ๋ค. ๋๊ฐ์ ์์ ์ง์ด ์๋ ๊ฒฝ์ฐ๋ ์ฐ๊ฒฐ๋ ๊ฒ์ด ์๋๋ค. <๊ทธ๋ฆผ 2>๋ <๊ทธ๋ฆผ 1>์ ๋จ์ง๋ณ๋ก ๋ฒํธ๋ฅผ ๋ถ์ธ ๊ฒ์ด๋ค. ์ง๋๋ฅผ ์ ๋ ฅํ์ฌ ๋จ์ง์๋ฅผ ์ถ๋ ฅํ๊ณ , ๊ฐ ๋จ์ง์ ์ํ๋ ์ง์ ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์๋ ์ง๋์ ํฌ๊ธฐ N(์ ์ฌ๊ฐํ์ด๋ฏ๋ก ๊ฐ๋ก์ ์ธ๋ก์ ํฌ๊ธฐ๋ ๊ฐ์ผ๋ฉฐ 5โคNโค25)์ด ์ ๋ ฅ๋๊ณ , ๊ทธ ๋ค์ N์ค์๋ ๊ฐ๊ฐ N๊ฐ์ ์๋ฃ(0ํน์ 1)๊ฐ ์ ๋ ฅ๋๋ค.
์ถ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์๋ ์ด ๋จ์ง์๋ฅผ ์ถ๋ ฅํ์์ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ ๋จ์ง๋ด ์ง์ ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ์์ค.
๐ก map์ด 1์ด ๋๋ ๋ถ๋ถ ์ฐพ์์ visited๊ฐ false์ด๋ฉด, bfs๋ฅผ ์คํํ์ฌ ํ ๋จ์ง๋ฅผ ์ฐพ์
๐ก ํ ๋จ์ง ๋ด์์ ์ด์ด์ ธ ์๋ ์ํํธ๋ฅผ ์ถ๊ฐํ๋ฉฐ, ์ํํธ์ ๊ฐ์๋ฅผ list์ ๋ฃ์
๐ก ๋์ด์ ธ ์๋ ๊ณณ์ ๋จ์ง(group)์ผ๋ก ๊ฐ์๋ฅผ ์
๐ก list๋ฅผ ์ ๋ ฌํ์ฌ ์ค๋ฆ์ฐจ์์ผ๋ก ์ถ๋ ฅํจ
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(map[i][j] == 1 && visited[i][j] == false) {
ret.add(bfs(i,j));
group++;
}
}
}
static int bfs(int x, int y) {
int apart = 1;
Queue<Node> q = new LinkedList<>();
q.add(new Node(x,y));
visited[x][y] = true;
while(!q.isEmpty()) {
Node cur = q.poll();
for(int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n)
continue;
if(map[nx][ny] == 1 && visited[nx][ny] == false) {
visited[nx][ny] = true;
q.add(new Node(nx, ny));
apart++;
}
}
}
}
group++;
Collections.sort(ret);
System.out.println(group);
for(int num : ret) {
System.out.println(num);
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;
public class Bruteforce_4 {
static int n;
static boolean[][] visited;
static int[][] map;
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int group = 0;
map = new int[n][n];
visited = new boolean[n][n];
List<Integer> ret = new ArrayList<>();
for(int i=0; i<n; i++) {
String[] s = br.readLine().split("");
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(map[i][j] == 1 && visited[i][j] == false) {
ret.add(bfs(i,j));
group++;
}
}
}
Collections.sort(ret);
System.out.println(group);
for(int num : ret) {
System.out.println(num);
}
}
static int bfs(int x, int y) {
int apart = 1;
Queue<Node> q = new LinkedList<>();
q.add(new Node(x,y));
visited[x][y] = true;
while(!q.isEmpty()) {
Node cur = q.poll();
for(int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n)
continue;
if(map[nx][ny] == 1 && visited[nx][ny] == false) {
visited[nx][ny] = true;
q.add(new Node(nx, ny));
apart++;
}
}
}
return apart;
}
static class Node{
int x;
int y;
Node(int x, int y){
this.x = x;
this.y = y;
}
}
}
์ฑ๊ณตโจ