백준 2667 : 단지번호붙이기 _자바 Java

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

 

DFS를 사용하였다.

 

1. 단지별 아파트 개수 저장에 배열 사용.

import java.io.*;
import java.util.*;

public class Main {
	
	static int N,cnt=0;
	static int[] apart;
	static int[][] arr;
	static boolean[][] check;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N =Integer.parseInt(br.readLine());
				
		arr= new int [N][N];
		check= new boolean [N][N];
		apart= new int[25*25];
		
        //배열 입력받기
		for(int i=0;i<N;i++) {
			String[] s = br.readLine().split("");
			for(int j=0;j<N;j++) {
				arr[i][j]=Integer.parseInt(s[j]);
			}
		}
		
		
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(arr[i][j]==1&&!check[i][j]) {
					cnt++;	//단지개수++
					dfs(i,j);
				}
			}
		}
				
		System.out.println(cnt);
		Arrays.sort(apart);	//오름차순 정렬
		for(int i : apart)
			if(i!=0)
				System.out.println(i);
		
		br.close(); 
		 
	}// main()
	
	static void dfs(int x,int y) {
		
		check[x][y]=true;
		apart[cnt]++;
		
		for(int i=0;i<4;i++) {
			int tX=x+dx[i];
			int tY=y+dy[i];
			
			if(tX>=0 && tY>=0 &&tX<N&&tY<N) {	//지도의 범위 내에서 
				if(!check[tX][tY]&&arr[tX][tY]==1) {	//방문한적이 없고, 집일떄
					dfs(tX,tY);
				}
			}
				
		}
	}//dfs() 


}// class Main

 

2. 단지별 아파트 개수 저장에 ArrayList사용.

import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static ArrayList<Integer> aList = new ArrayList<>();
	static int[][] arr;
	static boolean[][] check;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N =Integer.parseInt(br.readLine());
				
		arr= new int [N][N];
		check= new boolean [N][N];
		
		for(int i=0;i<N;i++) {
			String[] s = br.readLine().split("");
			for(int j=0;j<N;j++) {
				arr[i][j]=Integer.parseInt(s[j]);
			}
		}
		
		
		int k=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(arr[i][j]==1&&!check[i][j]) {
					aList.add(k,1);
					dfs(i,j,k);
					k++;
				}
			}
		}
				
		System.out.println(aList.size());
		Collections.sort(aList);
		for(int i : aList)
			System.out.println(i);
		
		br.close(); 
		 
	}// main()
	
	static void dfs(int x,int y,int k) {
		
		check[x][y]=true;
		
		for(int i=0;i<4;i++) {
			int tX=x+dx[i];
			int tY=y+dy[i];
			
			if(tX>=0 && tY>=0 &&tX<N&&tY<N) {	//지도의 범위 내에서 
				if(!check[tX][tY]&&arr[tX][tY]==1) {	//방문한적이 없고, 집일떄
					int a = aList.get(k);
					aList.set(k,a+1);
					dfs(tX,tY,k);
				}
			}
				
		}
	}//dfs() 


}// class Main