단지번호붙이기


백준 2667: 단지번호붙이기

문제보기
Alt text

풀이

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);
			}
		}
	}
}