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

 

 

---

https://n1tjrgns.tistory.com/245

[백준] 2667번 단지번호붙이기 Java (DFS, BFS)

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
	static int N;
	static int[][] xy;
	static boolean[][] visit;
	static int[] x_move = {-1,0,1,0};
	static int[] y_move = {0,-1,0,1};
	static int house_cnt = 0; //단지수
	static int[] house = new int[25*25];
	static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
	   	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	N = Integer.parseInt(br.readLine());
	   	xy = new int[N][N];
	   	visit = new boolean[N][N];
	   	for(int i = 0; i < N; i++) {
	   		String str = br.readLine();
	   		for(int j = 0; j < N; j++) {
	   			xy[i][j] = str.charAt(j) - '0';
	   		}
	   	}
	   	for(int i = 0; i < N; i++) {
	   		for(int j = 0; j < N; j++) {
	   			if(!visit[i][j] && xy[i][j] == 1) {
	   				dp(i,j,3);
	   				house_cnt++;
	   			}
	   		}
	   	}
	   	Arrays.sort(house);
	   	System.out.println(house_cnt);
	   	for(int i = 0; i < house.length; i++) {
	   		if(house[i] != 0)
	   		System.out.println(house[i]);
	   	}
	}
    static void dp (int x, int y, int direction) {
    	visit[x][y] = true; //1일 때 dp로 들어오는 조건으로 이미 처리된 좌표이다
    	int dir = 0; //검사한 방향 수
    	house[house_cnt]++;
    	while(dir < 4) {
    		int tx = x+x_move[direction];
    		int ty = y+y_move[direction];
    		if(tx >= N || tx < 0 || ty >= N || ty < 0) {
    			direction = change(direction);
    			dir++; //이 방향은 막혀있다
    			continue; //새로운 좌표를 구해야함
    		}
    		if(xy[tx][ty] == 1 && visit[tx][ty] == false) { //새로운 집을 찾았다면
    			dp(tx,ty,direction);
    		}
    		else {
    			direction = change(direction); //방향을 바꿔준다
    			dir++;
    		}
    	}
    }
    static int change(int n) {
    	if(n <= 0) {
    		return 3;
    	}
    	else
    		return n-1;
    }
}