on
[백준][Java] 2667번 단지번호붙이기 (DFS, BFS)
[백준][Java] 2667번 단지번호붙이기 (DFS, BFS)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
private static BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));
private static BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System . out ));
static int [][] complex;
static boolean [][] visited;
static List < Integer > list = new ArrayList < > ();
static int [] dx = { 0 , 0 , 1 , - 1 };
static int [] dy = { 1 , - 1 , 0 , 0 };
static int houseNum, N;
static void DFS( int y, int x) {
visited[y][x] = true ;
houseNum + + ;
for ( int k = 0 ; k < = 3 ; k + + ) {
int nx = x + dx[k];
int ny = y + dy[k];
if ( ! visited[ny][nx] & & complex[ny][nx] = = 1 ) {
DFS(ny, nx);
}
}
}
static void BFS( int y, int x) {
Queue < int [] > q = new LinkedList < > ();
q.offer( new int []{y,x});
visited[y][x] = true ;
while ( ! q.isEmpty()) {
int [] preXY = q.poll();
houseNum + + ;
for ( int k = 0 ; k < = 3 ; k + + ) {
int nx = preXY[ 1 ] + dx[k];
int ny = preXY[ 0 ] + dy[k];
if ( ! visited[ny][nx] & & complex[ny][nx] = = 1 ) {
q.offer( new int []{ny,nx});
visited[ny][nx] = true ;
}
}
}
}
public static void main( String [] args) throws IOException{
N = Integer. parseInt (br.readLine());
complex = new int [N + 2 ][N + 2 ];
visited = new boolean [N + 2 ][N + 2 ];
for ( int i = 1 ; i < = N; i + + ) {
char [] arr = br.readLine().toCharArray();
for ( int j = 1 ; j < = N; j + + ) {
complex[i][j] = arr[j - 1 ] - '0' ;
}
}
for ( int i = 1 ; i < = N; i + + ) {
for ( int j = 1 ; j < = N; j + + ) {
if ( ! visited[i][j] & & complex[i][j] = = 1 ) {
DFS(i, j);
// System.out.println(houseNum);
list. add (houseNum);
houseNum = 0 ;
}
}
}
// Collections.sort(list);
// System.out.println(list.size());
// for (Integer num : list) {
// System.out.println(num);
// }
//
list.clear();
visited = new boolean [N + 2 ][N + 2 ];
for ( int i = 1 ; i < = N; i + + ) {
for ( int j = 1 ; j < = N; j + + ) {
if ( ! visited[i][j] & & complex[i][j] = = 1 ) {
BFS(i, j);
// System.out.println(houseNum);
list. add (houseNum);
houseNum = 0 ;
}
}
}
Collections.sort(list);
System . out . println (list.size());
for (Integer num : list) {
System . out . println (num);
}
// bw.write("");
// bw.flush();
// bw.close();
}
}
from http://aig2029.tistory.com/279 by ccl(A) rewrite - 2021-09-15 23:01:47