BOJ 2667 단지번호붙이기

문제 분석

- 2차원 좌표에서 점점 퍼져나가면서 체크하기때문에 bfs로 구현한다. 

 

 

문제 풀이

1) 단지 수와 단지에 포함되는 아파트 수를 계산해야하기때문에 변수를 잘 설정해준다.

2) 만약 조건에 충족할 경우(map[i][j]==1  && !visited[i][j])는 단지를 ++해주고 bfs를 계산하러 간다.

3) bfs를 통해 탐색하고, 아파트의 개수를 apartNum배열에 해당 단지를 인덱스로 하여 ++해준다. 

4) bfs 탐색 후 각 아파트의 수가 들어있는 배열(apartNum)을 정렬하고(오름차순 출력을 위해), 단지를 출력 후 단지에 속하는 아파트의 수를 출력한다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	private static boolean[][] visited;
	private static int[] apartNum;
	private static int N, danNum;
	private static int[][] map;
	private static int[] dr = { -1, 1, 0, 0 }; // 좌우상하
	private static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visited = new boolean[N][N];
		apartNum = new int[N * N];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					danNum++;
					bfs(i, j);
				}
			}
		}
		Arrays.sort(apartNum);
		System.out.println(danNum);
		for (int i = 0; i < apartNum.length; i++) {
			if (apartNum[i] != 0) {
				System.out.println(apartNum[i]);
			}
		}

	}// main

	private static void bfs(int x, int y) {

		Queue<Point> q = new LinkedList<>();

		q.add(new Point(x, y));
		visited[x][y] = true;
		apartNum[danNum]++;

		while (!q.isEmpty()) {
			Point cur = q.poll();
			int curX = cur.x;
			int curY = cur.y;

			for (int d = 0; d < 4; d++) { // 상하좌우
				int nx = curX + dr[d];
				int ny = curY + dc[d];
				if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
					if (map[nx][ny] == 1 && !visited[nx][ny]) {
						q.add(new Point(nx, ny));
						visited[nx][ny] = true;
						apartNum[danNum]++;
					}
				}
			}
		}

	}// bfs

	static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

	}// Point
}// class-end