[TIL-25/01/22] 99클럽 코테 스터디 8일차 - 백준 2667: 단지번호붙이기 - JAVA

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

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

 

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

접근 방식

문제를 보면 맵 형태의 입력이 주어지고 `1`로 연결된 영역을 찾는 문제이다. 전형적인 BFS, DFS 탐색문제이다. 그러고 확인해야 하는게 dx, dy 테크닉이 적용된다는 것이다. 

 

문제에선 `1`이 연결된다는 것을 `상하좌우`로 지정했다. 그렇다는건 탐색 시 좌표이동은 `상하좌우`로 진행해야됨을 알 수 있다. 

 

코드(DFS)

package backjoon.silver.lv1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class B2667 {
    static int N;
    static boolean[][] visited;
    static char[][] map;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        visited = new boolean[N][N];
        map = new char[N][N];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        List<Integer> complexSizes = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == '1' && !visited[i][j]) {
                    int size = dfs(i, j);
                    complexSizes.add(size);
                }
            }
        }

        System.out.println(complexSizes.size());
        Collections.sort(complexSizes);
        for (Integer size : complexSizes) {
            System.out.println(size);
        }
    }

    private static int dfs(int x, int y) {
        visited[x][y] = true;
        int size = 1;

        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && map[nx][ny] == '1') {
                size += dfs(nx, ny);
            }
        }

        return size;
    }
}

 DFS 코드이다. 

 

위에선 말한건 처럼 다음과 같이 dx, dy를 상하좌우에 대해 선언을 한다. 

static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};

 

입력값을 받은 후 DFS을 돌기 위한 코드를 보면 다음과 같다. 

List<Integer> complexSizes = new ArrayList<>();
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (map[i][j] == '1' && !visited[i][j]) {
            int size = dfs(i, j);
            complexSizes.add(size);
        }
    }
}

문제에서 시작시점이 주어진 게 아니고 영역 별로 탐색이 끊기는 구조이므로 입력맵 어디서든 `dfs()`시작 될 수 있다. `dfs()`의 매개변수는 입력맵의 x, y 좌표이다.

 

대신 모든 값을 의미없이 돌 수 없으니 조건이 붙여 최소한으로 돌 수 있게한다.

• 입력 맵이 `1`인 경우
• 방문한적이 없는 경우

 

다음은 실 `dfs`로직이며, `dx,dy`을 이용해 해당 좌표 기준 `1`의 영역을 탐색하게 된다.

private static int dfs(int x, int y) {
    visited[x][y] = true;
    int size = 1;

    for (int i = 0; i < dx.length; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && map[nx][ny] == '1') {
            size += dfs(nx, ny);
        }
    }

    return size;
}

`size`에 경우 해당 영역에 `1`이 몇개인지 구하기 위한 변수로, `dfs`재귀가 돈다는 것은 `1`임을 이용하여 카운팅하게 된다.

 

마지막 출력 부분이며, `ArrayList`를 이용해 `1`의 영역의 갯수를 카운팅하고, `Collections.sort()`를 이용 오름차순 정렬이 이용해 다음과 같이 출력이 된다. 

List<Integer> complexSizes = new ArrayList<>();
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        ...
            complexSizes.add(size);
        ...
    }
}


System.out.println(complexSizes.size());
Collections.sort(complexSizes);
for (Integer size : complexSizes) {
    System.out.println(size);
}

 

코드(BFS)

이 문제는 BFS로도 접근이 가능하다. 

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

public class Main {

    private static final int[] DX = {1, -1, 0, 0};
    private static final int[] DY = {0, 0, 1, -1};
    private static int gridSize;
    private static char[][] map;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        gridSize = Integer.parseInt(br.readLine());

        map = new char[gridSize][gridSize];
        visited = new boolean[gridSize][gridSize];
        for (int i = 0; i < gridSize; i++) {
            map[i] = br.readLine().toCharArray();
        }

        List<Integer> complexSizes = new ArrayList<>();
        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                if (map[i][j] == '1' && !visited[i][j]) {
                    int size = bfs(i, j);
                    complexSizes.add(size);
                }
            }
        }

        System.out.println(complexSizes.size());
        complexSizes.stream()
                    .sorted()
                    .forEach(System.out::println);
    }

    private static int bfs(int startX, int startY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY});
        visited[startX][startY] = true;
        int size = 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            for (int i = 0; i < DX.length; i++) {
                int nx = x + DX[i];
                int ny = y + DY[i];

                if (isValidCell(nx, ny) && map[nx][ny] == '1' && !visited[nx][ny]) {
                    queue.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                    size++;
                }
            }
        }

        return size;
    }

    private static boolean isValidCell(int x, int y) {
        return x >= 0 && x < gridSize && y >= 0 && y < gridSize;
    }
}