Map이 주어지고, 탐색을 통해서 넓이나 지역의 수량을 찾는 문제 유형.

백준 Q2667

Sample Source Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static int N = 0;
	//static Stack<Integer[]> st;
	static int count = 0;
	
	public static void dfs(int r, int c, int[][] ck, int[][] map) {
		count++;
		ck[r][c] = 1; //방문 처리
		
		int[] _r = new int[] {0,0,1,-1};
		int[] _c = new int[] {1,-1,0,0};
	
		//st.add(new Integer[] {r, c});	
		//Integer[] curr = st.pop();

		for(int i=0;i<4;i++) {
			int new_r = r + _r[i];
			int new_c = c + _c[i];
			if(new_r > N || new_c >N || new_r <0 || new_c<0 ) continue;
			
			if(ck[new_r][new_c]==0 && map[new_r][new_c]==1){
				dfs(new_r, new_c, ck, map);
			}
		}
		
	}
	
	public static void main(String[] args) {
	

		try {
			// 입력 처리
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			N 	= Integer.parseInt(st.nextToken());
			
			int[][] map	= new int[N+1][N+1];
			int[][] ck	= new int[N+1][N+1];
			
			//st = new Stack<Integer[]>();
			 
			for(int i=1;i<=N;i++) {
				String str = br.readLine();
				for(int j=0;j<str.length();j++) {
					//map[i][j+1] = str.charAt(j) - '0'; //방법 1
					map[i][j+1] = Character.getNumericValue(str.charAt(j)); //방법 2
				}
			}
	
			//System.out.println(Arrays.toString(map));
			
			int zone = 0;
			ArrayList<Integer> al = new ArrayList();
			
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {	
					//System.out.format("%d, %d \n",i,j);
					if( map[i][j] == 1 && ck[i][j] == 0 ){ 
						zone++;
						count = 0;
						dfs(i, j, ck, map);						
						al.add(count);
					}
					
				}
			}
			
			//Arrays.sort();
			Collections.sort(al);
			
//			System.out.println("Zone 	: "+zone);
//			System.out.println("Count 	: "+al.toString());
//			System.out.println("END");
			
			System.out.println(zone);
			for(int i=0;i<al.size();i++)
				System.out.println(al.get(i));
		}catch(Exception e) {
			e.printStackTrace();
		}
	
	}
}
/*
입력
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

출력
3
7
8
9

*/

참고