[백준] 단지번호붙이기 - Silver 1

[jusung-c]

문제 링크

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

문제 조건

정사각형 지도에 1과 0이 채워져 있다.

• 상하좌우로 연결된 1들을 하나의 단지로 묶어서 번호를 붙이자
• 단지 수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 정렬해 출력하라

---

아이디어

정답의 최대치

1. 단지의 개수가 최대치인 경우

N의 최댓값이 25이므로 단지의 개수가 최대일 경우 25^2 / 2이다. int 자료형으로 충분하다.

2. 한 단지 안 집의 개수가 최대치인 경우

N의 최댓값이 25이므로 집의 개수가 최대일 경우는 25^2이다. int 자료형으로 충분하다.

정점과 간선이 주어진 문제와 다르게 격자형의 0과 1로 이루어진 map이 주어졌다.

격자형 그래프 구성
5개의 격자 지도를 다음처럼 격자형 그래프로 나타낼 수 있다.
(i,j) 위치에 있는 점을 기준으로 집이 있으면 흰색, 없으면 회색으로 표현한다. 각 점과의 간선은 상하좌우로 인접했을 경우 연결해주면 된다.

각 점들에 대해서 상하좌우를 모두 탐색해야 한다. 미리 배열에 상하좌우를 탐색할 수 있도록 저장해둔다.

결과적으로 만들어지는 격자형 그래프는 다음과 같다.

격자형 그래프에 대해 탐색을 진행한다.

1. 왼쪽 위에서부터 방문한다. 집이 없으므로 다음 위치로 넘어간다.
2. 방문한 적이 없는 집을 만났으므로 이 집을 시작점으로 인접한 모든 집들을 탐색해 새로운 단지로 묶고, 방문 처리를 한다.
3. 동시에 묶인 집들의 개수를 센다.
4. 위의 과정을 반복한다.

---

시간 복잡도

격자형 그래프의 정점의 개수는 N^2개이고, 간선의 개수는 각 정점마다 상하좌우로 4개의 간선이 있을 수 있으므로 최대 N^2*4일 것이다.

BFS이든 DFS이든 간선을 인접 리스트 형식으로 관리하게 되면 시간 복잡도는 O(V+E) 이므로 최종 시간 복잡도는 O(N^2)이 될 것이다.

---

DFS 구현

import java.io.*;
import java.util.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, grout_cnt;
    static String[] input;
    static boolean[][] visit;
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static ArrayList<Integer> group;

    public static void init() throws IOException {

        N = Integer.parseInt(br.readLine());
        input = new String[N];

        for (int i = 0; i < N; i++) {
            input[i] = br.readLine();
        }

        visit = new boolean[N][N];
    }

    private static void pro() throws IOException {
        group = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 방문하지 않은 집 발견
                if (!visit[i][j] && input[i].charAt(j) == '1') {
                    // 단지 안 집 개수
                    grout_cnt = 0;

                    // 연결된 집 모두 탐색
                    dfs(i, j);

                    group.add(grout_cnt);
                }
            }
        }

        Collections.sort(group);

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

        for (Integer integer : group) {
            bw.write(integer + "\n");
        }
    }

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

        visit[x][y] = true;
        grout_cnt++;

        for (int d = 0; d < 4; d++) {
            int nx = x + dir[d][0];
            int ny = y + dir[d][1];

            // 새로 이동한 좌표 범위 체크
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

            // 새로 이동한 좌표에 집이 있는지 체크
            if (input[nx].charAt(ny) == '0') continue;

            // 방문 여부 체크
            if (visit[nx][ny]) continue;

            dfs(nx, ny);
        }

    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}

BFS 구현

import java.io.*;
import java.util.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, g_cnt;
    static String[] input;
    static boolean[][] visit;
    static int[][]dir= {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static List<Integer> group = new ArrayList<>();

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void init() throws IOException {
        N = Integer.parseInt(br.readLine());
        input = new String[N];
        visit = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            input[i] = br.readLine();
        }
    }

    private static void pro() throws IOException {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 방문 안 한 집 찾기
                if (!visit[i][j] && input[i].charAt(j) == '1') {
                    g_cnt = 0;

                    bfs(i, j);

                    group.add(g_cnt);
                }
            }
        }

        Collections.sort(group);
        bw.write(group.size() + " ");
        bw.newLine();
        for (int i : group) {
            bw.write(i + " ");
            bw.newLine();
        }
    }

    private static void bfs(int x, int y) {
        Queue<Point> que = new LinkedList<>();

        g_cnt = 1;
        que.add(new Point(x, y));
        visit[x][y] = true;

        while (!que.isEmpty()) {
            Point p = que.poll();

            for (int d = 0; d < 4; d++) {
                int nx = p.x + dir[d][0];
                int ny = p.y + dir[d][1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                if (input[nx].charAt(ny) == '0') continue;

                if (visit[nx][ny]) continue;

                que.add(new Point(nx, ny));
                visit[nx][ny] = true;
                g_cnt++;
            }
        }

    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}