Java 2667 단지번호붙이기

 

 

풀이 : 

문제를 보고 생각한 풀이는 dfs로 접근하는 것이었습니다.

지도 정보를 2차원 배열로 입력 받은 뒤, 모든 원소를 돌면서 방문한 원소가 이미 방문한 원소거나, 값이 0일 경우에는 재귀함수를 호출하지 않고, 방문하지 않았거나 값이 1일 경우에는 집의 개수를 세는 static 변수를 0으로 초기화한 뒤 재귀함수를 호출해 해당 원소의 상, 하, 좌, 우의 인접한 원소들을 검사하여 방문하지 않았거나 값이 1일 경우에는 다시 재귀함수를 호출해 집의 개수를 세어주고 함수호출이 종료되면 카운트했던 집의 개수를 ArrayList에 저장해주고 모든 원소의 탐색이 종료될 때 list의 사이즈를 출력하고 list를 오름차순으로 정렬한 값을 하나씩 출력하여 해당 문제를 풀이하였습니다.

 

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

public class Main {

    static int n, tmp;
    static int[][] map;
    static boolean[][] visited;
    static int cnt;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

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

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

        for(int i = 0; i < n; i++){
            String str = br.readLine();
            for(int j = 0; j < n; j++){
                map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
            }
        }

        ArrayList<Integer> list = new ArrayList<>();

        for(int i = 0; i < n; i++){
            for (int j = 0; j < n; j++) {
                if(!visited[i][j] && map[i][j] == 1){
                    tmp = 0;
                    dfs(i, j);
                    list.add(tmp);
                }
            }
        }

        System.out.println(list.size());
        list.sort(null);
        for(int i : list){
            System.out.println(i);
        }
    }
    static void dfs(int x, int y){
        visited[x][y] = true;
        tmp++;

        for(int i = 0; i < 4; i++){
            int dxs = dx[i] + x;
            int dys = dy[i] + y;

            if(dxs < 0 || dxs >= n || dys < 0 || dys >= n){
                continue;
            }
            if(visited[dxs][dys] || map[dxs][dys] == 0){
                continue;
            }
            dfs(dxs,dys);
        }
    }
}