[알고리즘-자바] 백준 2667번 단지번호붙이기

문제

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

2667번: 단지번호붙이기

언어

자바 JAVA

로직

동서남북

현재 위치에서 동서남북으로 이동하면서 이웃된 집이 있는지 확인한다.

static int[] dx = {1, -1, 0, 0}; // 동:1, 서:-1
static int[] dy = {0, 0, 1, -1}; // 남:1, 북:-1

탐색 시작 위치

탐색을 시작할 위치(단지)를 찾는다. 주어진 구간 내에 위치하면서 방문한 적이 없는 위치를 찾는다.

해당 위치를 큐에 저장하고 방문 처리 및 count(단지 내의 집의 개수)를 1증가시킨다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (apartment[i][j] == 1 && !visited[i][j]) {
            Queue<int[]> que = new LinkedList<>();
            que.offer(new int[]{i, j});
            visited[i][j] = true;
            count += 1;

            .. 생략
        }
    }
}

단지 내의 집 개수

큐에서 값을 꺼낸 위치에서 동서남북 모두 이동해보면서 붙어 있는 집이 존재하는지 확인한다. 

집이 구간 내에 존재하면서 방문한 적이 없다면 해당 위치를 큐에 저장하고 방문처리 한다. 그리고 단지 내의 집의 개수(count)를 1증가 시킨다.

while (!que.isEmpty()) {
    int[] poll = que.poll();
    int curX = poll[0];
    int curY = poll[1];

    for (int k = 0; k < 4; k++) {
        int tmpX = curX + dx[k];
        int tmpY = curY + dy[k];
        if (tmpX >= 0 && tmpX < n && tmpY >= 0 && tmpY < n) {
            if (!visited[tmpX][tmpY] && apartment[tmpX][tmpY] == 1) {
                que.offer(new int[]{tmpX, tmpY});
                visited[tmpX][tmpY] = true;
                count++;
            }
        }
    }
}

---

최종 코드

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

public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited;
    static int n;
    static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        n = Integer.parseInt(br.readLine());

        int[][] apartment = new int[n][n];
        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < n; j++) {
                apartment[i][j] = input.charAt(j) - '0';
            }
        }

        bfs(apartment);

        Collections.sort(list);
        sb.append(list.size() + "\n");
        for (int num : list) {
            sb.append(num + "\n");
        }

        System.out.println(sb);

    }

    static void bfs(int[][] apartment) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (apartment[i][j] == 1 && !visited[i][j]) {
                    Queue<int[]> que = new LinkedList<>();
                    que.offer(new int[]{i, j});
                    visited[i][j] = true;
                    count += 1;

                    while (!que.isEmpty()) {
                        int[] poll = que.poll();
                        int curX = poll[0];
                        int curY = poll[1];

                        for (int k = 0; k < 4; k++) {
                            int tmpX = curX + dx[k];
                            int tmpY = curY + dy[k];
                            if (tmpX >= 0 && tmpX < n && tmpY >= 0 && tmpY < n) {
                                if (!visited[tmpX][tmpY] && apartment[tmpX][tmpY] == 1) {
                                    que.offer(new int[]{tmpX, tmpY});
                                    visited[tmpX][tmpY] = true;
                                    count++;
                                }
                            }
                        }
                    }
                    list.add(count);
                    count = 0;
                }
            }
        }
    }
}