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

---

풀이)

안녕하세요 dfs 멍충이 야미입니다

아 정말 못하네~^0^

 

이 문제는 인접행렬을 사용하였다

단지를 인덱스로 갖는 배열로 만들고 그 배열에 단지내 수를 저장한다 -> house

나중에 이 배열의 size가 곧 총 단지 수가 된다

 

그리고 방문처리를 해주며 dfs를 통해 해결했다

 

아래는 코드!

 

 

자바 코드)

import java.util.*;


public class Main {
    static int n;
    static int count;
    static int[][] arr;
    static boolean[][] visited;

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

    static ArrayList<Integer> house = new ArrayList<>(); // 단지별 집의 개수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

        for(int i=0;i<n;i++) {
            String input = sc.next();
            for (int j = 0; j < n; j++) {
                arr[i][j] = input.charAt(j) - '0';
            }
        }

        count = 0;

        for(int i=0;i<n;i++) { //단지 별 dfs 호출
            for (int j = 0; j < n; j++) {
                if(arr[i][j]==1 && !visited[i][j]) {
                    count=1;
                    dfs(i,j);
                    house.add(count);
                }
            }
        }
        Collections.sort(house);
        System.out.println(house.size());
        for(int num : house) {
            System.out.println(num);
        }
    }

    public static int dfs(int x, int y) {
        visited[x][y] = true;

        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) { //한 단지 내에서 dfs 호출
                if(arr[nx][ny]==1 && !visited[nx][ny]) {
                    dfs(nx, ny);
                    count++;
                }
            }
        }
        return count;
    }

}

먼저 단지 정보를 입력받을 때 띄어쓰기 없이 입력이 되기 때문에 이를 String으로 입력받고 하나씩 띄어서 배열에 저장해준다

그리고 이코테였나? 에서 상하좌우 이동할 때는 dx, dy 배열에 저장해서 사용하는게 좋다고 했던 것 같아서 저장하고 사용했다

그리고 dfs 재귀를 사용해서 호출했다

끝!