[백준] 2667번 : 단지번호붙이기 - JAVA [자바]

https://www.acmicpc.net/problem/2667

---

dfs 알고리즘 문제이다.

1. 집 배열을 탐색하면서 1(집이 있으)면서 아직 방문하지 않은 집이면 방문한다.
2. 방문한 집의 상하좌우를 탐색하며 1(집이 있으)면서 아직 방문하지 않은 집이면 방문한다.

이 두 가지를 반복하면서 구하면 된다.

1 번은 집 배열을 탐색하면서 if (house[i][j] && !visited[i][j]) 인 집을 찾으면 된다.

2번의 상하좌우 집을 탐색을 어떻게 할까?

static int[] xMove = {0, 0, -1, 1};
static int[] yMove = {-1, 1, 0, 0};

현재 x 에서 왼쪽을 보려면 x = x-1, y = y 를 대입하면 된다.
즉,

int newX = x + xMove[2];
int newY = y + yMove[2];

새로 생긴 newX와 newY는 (x,y)에서 (x-1,y)로 바뀌며 좌측에 있는 칸을 볼 수 있다. 이러한 개념을 토대로 Move 배열의 0 ~ 3번째까지 차례대로 더해주면 x,y 의 상하좌우의 칸을 탐색할 수 있다.

for (int i = 0; i < 4; i++) {
	int newX = x + xMove[i];
	int newY = y + yMove[i];
	// 주어진 칸 안에 있는 곳 일때
	if (newX >= 0 && newX < N) {
    	if (newY >= 0 && newY < N) {
        	// 탐색하는 칸이 집이 있으며(true) 아직 방문하지 않은 곳이라면
        	if (house[newX][newY] && !visited[newX][newY]) {
            	dfs(newX, newY);
			}
		}
	}
}

그 후 상하좌우가 칸을 벗어난 범위인지 확인한다.
그 다음 그 칸에 집이 있는지 확인하고 아직 방문하지 않았는지 확인한다.
집이 있고 아직 방문하지 않았다면 다음 dfs 알고리즘으로 그 칸을 넘겨준다.
그러면 상하좌우로 이어져있는 (문제에서 말하는) 단지를 형성하게 되고 방문할때 마다 count++ 를 해주었기 때문에 이 단지의 총 집 수를 알 수 있다.

또한, 상하좌우에 인접한 집이 없다는 것은 이 칸에서 갈 수 있는 칸은 없다는 뜻이 되고 전의 칸으로 돌아간다.
이 알고리즘이 반복되며 하나의 단지를 형성하며 단지의 집 수도 계산한다.

---

public class bj2667 {

    public static int N, count = 0;
    public static boolean[][] house;
    public static boolean[][] visited;
    static int[] xMove = {0, 0, -1, 1};
    static int[] yMove = {-1, 1, 0, 0};

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

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N][N];
        house = new boolean[N][N];
        ArrayList<Integer> countHouse = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            char[] charArray = line.toCharArray();
            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(String.valueOf(charArray[j]));
                if (num == 1) {
                    house[i][j] = true;
                } else house[i][j] = false;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 1 이며 아직 방문하지 않은 집이면 탐색시작
                if (house[i][j] && !visited[i][j]) {
                	// 단지 카운트 0으로 초기화하고 시작
                    count = 0;
                    dfs(i, j);
                    countHouse.add(count);
                }
            }
        }

        Collections.sort(countHouse);

        bw.write(countHouse.size() + "\n");

        for (int count : countHouse) {
            bw.write(count + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int x, int y) {
        // 방문 처리
        visited[x][y] = true;
        count++;

        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int newX = x + xMove[i];
            int newY = y + yMove[i];
            // 주어진 칸 안에 있는 곳 일때
            if (newX >= 0 && newX < N) {
                if (newY >= 0 && newY < N) {
                    // 탐색하는 칸이 집이 있으며(true) 아직 방문하지 않은 곳이라면
                    if (house[newX][newY] && !visited[newX][newY]) {
                        dfs(newX, newY);
                    }
                }
            }
        }
    }
}