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

* www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

내 풀이

 

1로 연결된거면 같은 단지니까 재귀적으로 이를 풀기로 했다.

 

public class BOJ_2667{
	static int[] dx = { 0, 0, -1, 1 }; // 0:좌, 1:우, 2:상, 3:하
	static int[] dy = { -1, 1, 0, 0 };

	static int N; // 단지 수
	static int[][] danji; // 단지
	static boolean[][] visited;	//단지에 방문했는지 검사할 배열
	static int[] answer = new int[25 * 25];	// 정답 넣을 배열
	static int danjiNum = 0;// 단지 개수 

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(in.readLine());
		danji = new int[N][N]; // 단지
		visited = new boolean[N][N]; // 단지에 방문했는지 저장하는 배열

		// init danji
		for (int i = 0; i < N; i++) {
			String s = in.readLine();
			for (int j = 0; j < N; j++) {
				danji[i][j] = s.charAt(j) - '0';
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 단지가 있고 아직 방문하지 않았다면
				if (danji[i][j] == 1 && visited[i][j] == false) {
					// 단지를 찾았으니 단지 수를 하나 증가시킨다.
					danjiNum++;
					// 단지 내 아파트 수를 구한다.
					getDanji(i, j);
				}
			}
		}
		
		//출력
		System.out.println(danjiNum);
		Arrays.sort(answer);	// 오름차순 출력이므로 정렬
		for(int a:answer) {
			if(a==0) continue;
			else System.out.println(a);
		}
	}

	// 좌표가 단지 내에 있는지 확인
	static boolean isInside(int x, int y) {
		if (x >= 0 && x < N && y >= 0 && y < N)
			return true;
		return false;
	}

	// 재귀적으로 단지 찾기
	// (x,y)는 아직 방문하지 않은 단지의 좌표
	static void getDanji(int x, int y) {
		//1. (x,y) 단지 방문 처리
		visited[x][y] = true;
		//2. 아파트를 찾았으므로 수 증가
		answer[danjiNum]++;

		for (int i = 0; i < 4; i++) {
			// 상하좌우 이동
			int newX = x + dx[i];
			int newY = y + dy[i];
			// 지도 내에 있는 아직 방문하지 않은 단지
			if (isInside(newX, newY) && danji[newX][newY] == 1 && visited[newX][newY] == false) {
				// 해당 좌표에서도 단지를 찾는다.
				getDanji(newX, newY);
			}
		}

	}

}