質問元:[BOJ 2667]番号だけ貼って、https://www.acmicpc.net/problem/2667

👨‍🏫質問する

図1に示すように、正方形の地図があります.1は家がある場所、0は家がない場所を表します.哲洙はこの地図で団地を定義しようとしたが、それはつながった家の集合であり、団地番号を与えた.ここでつながっているのは、ある家に左右や上下の異なる家があることを意味します.対角線に家がある場合はつながっていません.<【図2】<図1>を単一番号で示す図である.地図を入力してセル数を出力し、各セルの家屋数を昇順に並べてプログラムを作成してください.

入力

1行目は地図サイズN(正方形、横方向と縦方向のサイズが同じ、5≦N≦25)を入力し、次の行は各N個の資料(0または1)を入力する.

しゅつりょく

最初のローの合計出力数.その後、各園区内の家屋の数を昇順に並べ、各行に1つ出力します.

サンプルI/O

入力例
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
サンプル出力
3
7
8
9

💻コード#コード#

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

public class DanG {
    static int[][] map;
    static boolean[][] visited;
    static int[] location;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

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

        for(int i = 0; i < N; i++){
            String line = br.readLine();

            for(int j = 0; j < line.length(); j++){
                map[i][j] = line.charAt(j) - '0';
            }
        }

        /*
         * 지도를 순회하다 방문하지 않은 집이 있을 경우,
         * 해당 좌표를 기준으로 search 메서드 호출
         */
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(visited[i][j] == false && map[i][j] == 1){
                    list.add(search(new int[] {i, j}));
                }
            }
        }

        // 단지의 크기가 작은 순서부터 출력해야 하므로 오름차순 정렬
        Collections.sort(list);

        sb.append(list.size() + "\n");

        for(int i = 0; i < list.size() - 1; i++){
            sb.append(list.get(i) + "\n");
        }

        sb.append(list.get(list.size() - 1));

        System.out.println(sb);
    }

    // 단지에 있는 집의 수를 반환해주는 메서드
    static int search(int[] location){
        int[] dy = {-1, 0, 1, 0};
        int[] dx = {0, 1, 0, -1};
        int y = location[0];
        int x = location[1];

        Stack<int[]> stack = new Stack<>();

        // 단지 내 집의 수를 저장해 줄 변수
        int count = 0;

        visited[y][x] = true;
        stack.push(location);
        count++;

        while(!stack.isEmpty()){
            int[] peek = stack.peek();
            boolean flag = false;

            // 현재 좌표를 기준으로 상 하 좌 우 확인
            for(int i = 0; i < 4; i++){
                int ny = peek[0] + dy[i];
                int nx = peek[1] + dx[i];

                /*
                 * 상 하 좌 우 검사 시 배열의 범위를 벗어나지 않는지 확인
                 * 방문한 적이 없는 집인 경우 stack에 push하고, 해당 좌표를 방문 처리
                 */
                if(isBound(new int[]{ny, nx}) && visited[ny][nx] == false && map[ny][nx] == 1){
                    stack.push(new int[]{ny, nx});
                    visited[ny][nx] = true;
                    flag = true;
                    count++;
                    break;
                }
            }

            // 근처에 더 이상 방문할 집이 없을 경우 stack에서 pop
            if(!flag){
                stack.pop();
            }
        }

        return count;
    }

    // 상 하 좌 우를 검사 할 때 배열의 길이를 넘는지 확인해주는 함수
    static boolean isBound(int[] location){
        if((location[0] >= 0 && location[1] >= 0) && 
        (location[0] < map.length && location[1] < map[0].length)){
            return true;
        }

        return false;
    }
}

💡ポスト

深さ優先探索(DFS)または幅優先探索(BFS)を利用することは解決可能な問題である.
個人的には探索問題をするとき、DFSもBFSも解けるなら、BFSを利用した方が個人的に分かりやすいので、BFSの方が好きですが、DFSはまだ慣れていないのでDFSで解いてみます.😁
もう少し探索問題を作って、DFSに慣れた時にbacktracking問題に挑戦しましょう!