백준-2667 단지번호붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

DFS로 풀이하였다

map을 순회하다 ****1인지점발견 & 방문하지않음**** 이면 dfs를 통해 1로 이어진 끝까지 탐색후 종료.

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class 단지번호붙이기 {
	static int N;
	static int [][]arr;
	static boolean [][] visit;
	static int ans;//단지수
	static int [] aparts = new int [25*25];//임의의 수 지정하여 아파트의 수를 저장할 배열, 충분히 큰값으로 해주지않으면 단지수가많아졌을때 ARrayoutofindex에러
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/단지번호붙이기.txt"));
		Scanner sc = new Scanner(System.in);
		N =sc.nextInt();//배열의 크기
		arr = new int [N+1][N+1];
		visit = new boolean[N+1][N+1];
		ans=0;//단지의수
		for (int i = 1; i <= N; i++) {//-'0'해주어 숫자형으로 저장
			String str = sc.next();
			for (int j = 1; j <= N; j++) {
				arr[i][j]= str.charAt(j-1)-'0';
			}
		}
//		print();//배열입력확인
		for (int i = 1; i <=N ; i++) {//1,1부터 탐색시작
			for (int j = 1; j <= N; j++) {
				if(arr[i][j]==1 && !visit[i][j]) {//만약 arr[i][j]값이 1이고 방문되지않았다면
					ans++;//단지수//단지수를 +1
					dfs(i,j);	//근처1을찾기위해 dfs시작
				}
			}
		}
		Arrays.sort(aparts);//아파트의수를 오름차순으로 출력하기위해 sort
		System.out.println(ans);//단지의 수 출력
		
		for (int i = 0; i < aparts.length; i++) {
			if(aparts[i]==0) continue;//아파트 배열의 값이 0인경우 continue
			else {//0이아닌경우 아파트의 수 출력
				System.out.println(aparts[i]+" ");
			}
			
		}
	}
	private static int [] dr = {-1,1,0,0};//상하좌우
	private static int [] dc = {0,0,-1,1};
	private static void dfs(int x, int y) {
        visit[x][y] = true;//방문체크
        aparts[ans]++;//아파트의 수를 저장할 배열에 단지의 인덱스에 아파트의수+1

        for(int i=0; i<4; i++){//사방탐색
            int nx = x + dr[i];
            int ny = y + dc[i];

            if(nx >=1 && ny >=1 && nx <= N && ny <=N ){
                if(arr[nx][ny] == 1 && !visit[nx][ny]){//근처가 1이고 방문되지않았다면 dfs진행
                    dfs(nx,ny);
                }
            }
        }
    }
	public static void print() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(arr[i][j]+" ");
			}System.out.println();
		}
	}

}