[문제풀이] 백준 2667 단지번호붙이기

//단지 번호붙이기 (DFS 버전) package graph1; import java.util.*; public class pro_2667 { static int a[][]; static int dx[] = {1,0,-1,0}; static int dy[] = {0,1,0,-1}; static int cnt=2; static int n; static int sum[]; static void dfs(int x, int y){ a[x][y]=cnt; sum[cnt]++; for(int i=0;i<4;i++){ if(x+dx[i]<n && x+dx[i]>=0 && y+dy[i]<n && y+dy[i]>=0){ if(a[x+dx[i]][y+dy[i]]==1) dfs(x+dx[i],y+dy[i]); } } } public static void main(String args[]){ Scanner sc = new Scanner(System.in); n=sc.nextInt(); a=new int[n][n]; sum=new int[n*n]; for(int i=0;i<n;i++){ String str = sc.next(); char ch[]=str.toCharArray(); for(int j=0;j<ch.length;j++){ a[i][j]=ch[j]-'0'; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(a[i][j]==1){ dfs(i,j); cnt++; } } } Arrays.sort(sum); System.out.println(cnt-2); for(int i=n*n-cnt+2;i<n*n;i++){ System.out.println(sum[i]); } } }

//단지 번호붙이기 (BFS 버전) package graph1_복습; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pair{ //큐에 x,y 짝을 저장하기 위한 class int x,y; Pair(int x, int y){ this.x=x; this.y=y; } } public class 단지번호붙이기_2667 { static int dx[]={0,0,1,-1}; static int dy[]={1,-1,0,0}; static int count; static int result[]; static int arr[][]; static int N; static void bfs(int x, int y){ Queue<Pair> q = new LinkedList<Pair>(); q.add(new Pair(x,y)); arr[x][y]=count; while(!q.isEmpty()){ Pair tmp=q.remove(); result[count]++; for(int i=0;i<4;i++){ int cx=dx[i]+tmp.x; int cy=dy[i]+tmp.y; if(cx>=0 && cx<N && cy>=0 && cy<N){ if(arr[cx][cy]==1){ q.add(new Pair(cx,cy)); arr[cx][cy]=count; } } } } } public static void main(String args[]){ Scanner sc = new Scanner(System.in); N=sc.nextInt(); arr=new int[N][N]; result=new int[N*N]; for(int i=0;i<N;i++){ String tmp=sc.next(); char ch[]=tmp.toCharArray(); for(int j=0;j<ch.length;j++){ arr[i][j]=ch[j]-'0'; } } count=2; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(arr[i][j]==1){ bfs(i,j); //System.out.println(" "); count++; } } } System.out.println(count-2); Arrays.sort(result); for(int i=N*N-count+2;i<N*N;i++){ System.out.println(result[i]); } } }