백준-2667번/단지번호붙이기(java)

 

문제 이해

 

연결성분을 구하는 과정과 유사하기 때문에 dfs의 성질을 이용하여 풀어야겠다고 생각 하였다.

이동은 위,아래,좌,우 만 가능하다

따라서 이차원 배열에서 x좌표를 +1,-1하거나 y좌표를 +1,-1하는 방식으로 이동을 할 수 있다는 뜻이다.

 

문제 해결

 

<위,아래로 움직일 수 있도록 해주는 배열 dx,dy>

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

 

<dfs 구현>

public static void dfs(int x, int y) {
    arr[x][y] = 0;
    count += 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < N && ny >= 0 && ny < N && arr[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}

 

arr[dx][dy]가 1 일때만 이동하여서 연결성분을 알아낼수있도록 하였고, if문에 조건을 넣어서 배열의 영역을 벗어나지 않도록 하였고, count값을 집에 방문 할때마다 증가시켜줬다.

count ==> 단지 내 집의 수

 

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (arr[i][j] == 1) {
            count = 0;
            dfs(i, j);
            Home.add(count);
            danji++;
        }
    }
}

메인 함수에서는 배열을 순회하면서 dfs 수행하고 count를 ArrayList에 추가해준다.

 

<전체 코드>

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

public class Problem2667_2 {
    static int N, count;
    static int[][] arr;
    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());
        arr = new int[N][N];
        ArrayList<Integer> Home = new ArrayList<>();
        int danji = 0;

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    count = 0;
                    dfs(i, j);
                    Home.add(count);
                    danji++;
                }
            }
        }

        Collections.sort(Home);

        System.out.println(danji);
        for (int i : Home) {
            System.out.println(i);
        }
    }

    public static void dfs(int x, int y) {
        arr[x][y] = 0;
        count += 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N && arr[nx][ny] == 1) {
                dfs(nx, ny);
            }
        }
    }
}