단지번호붙이기
백준 2667: 단지번호붙이기
풀이
DFS 이용
char형을 int형으로 변환하는 법
-> char - ‘0’
소스코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
static int N;
static int[][] map;
static boolean[][] visited;
static ArrayList<Integer> list;
static int[] dr = {-1,1,0,0};
static int[] dc = {0,0,-1,1};
static int cnt;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
map = new int[N][N];
visited = new boolean[N][N];
list = new ArrayList<>();
for(int i=0; i<N; i++) {
String str = sc.next();
for(int j=0; j<N; j++) {
char ch = str.charAt(j);
map[i][j] = ch-'0'; //char형을 int형으로
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(map[i][j]==1 && !visited[i][j]) {
cnt =0;
dfs(i, j);
list.add(cnt);
}
}
}
Collections.sort(list); //리스트 정렬(오름차순)
System.out.println(list.size());
for(int i=0; i<list.size(); i++)
System.out.println(list.get(i));
}
static void dfs(int i, int j) {
cnt++;
visited[i][j] = true;
for(int d =0; d<4; d++) {
int nr = i+dr[d];
int nc = j+dc[d];
if(nr>=0 && nc>=0 && nr<N && nc<N && !visited[nr][nc] && map[nr][nc]==1) {
dfs(nr, nc);
}
}
}
}