[자바] 백준 2667번 단지번호붙이기

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

 

모든 2차원 배열을 탐색하면서 인접한 경우에 대해 단지로 묶는 문제였다. DFS, BFS 문제 중에서 개인적으로 많이 어렵게 느끼는 dx, dy 사용해서 상하좌우 탐색하고, 인접한 경우에 대해 판별해야하는 문제이다. 전에 풀었던 문제에서 많이 익숙해져서 동일하게 풀었는데 풀면서 헷갈렸던 부분은 어디서부터 cnt를 늘려줘야할지였다. 처음에 cnt는 1로 초기화해두고 (dfs에 들어가는 순간 단지에 하나의 가구는 포함된 상태) 시작하고, dfs 함수 내에서 cnt를 증가시켜주고 가장 먼저 dfs를 호출한 main 함수 내에 있는 dfs의 실행이 끝나면, cnt를 ArrayList에 add 하여 값을 저장한다. 총 단지의 수는 각 단지의 가구 수를 저장할 ArrayList를 만들어주고 이에 대한 size값을 구하면 됐다. 오름차순도 해야되므로 Collections 사용해서 sort()로 정렬해줬다.

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

public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] visited;
    static int[][] graph;
    static ArrayList<Integer> answer = new ArrayList<>();
    static int cnt = 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        graph = new int[t][t];
        visited = new boolean[t][t];

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

        for(int i = 0; i < t; i++){
            for(int j = 0; j < t; j++){
                if(graph[i][j] == 1 && !visited[i][j]){
                    dfs(i, j);
                    answer.add(cnt);
                    cnt = 1;
                }
            }
        }

        Collections.sort(answer);

        bw.write(String.valueOf(answer.size()));
        bw.newLine();
        for(int i = 0; i < answer.size(); i++){
            bw.write(String.valueOf(answer.get(i))+ "\n");
        }
        bw.flush();

        bw.close();
    }

    static void dfs(int x, int y){
        visited[x][y] = true;
        int next_x, next_y;
        for(int i = 0; i < 4; i++){
            next_x = x + dx[i];
            next_y = y + dy[i];

            if(next_x < graph.length && next_y < graph.length && next_y >= 0 && next_x >= 0){
                if(graph[next_x][next_y] == 1 && !visited[next_x][next_y]){
                    cnt++;
                    dfs(next_x, next_y);
                }
            }
        }
    }

}