Algorithm

[BOJ 2667] 단지번호붙이기 ( with Java )

quedevel 2023. 4. 16. 14:20
728x90
반응형

문제

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

제출한 답안

package BOJ;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class BOJ_2667 {
    private static int[] dx = {0,0,1,-1};
    private static int[] dy = {1,-1,0,0};
    private static int[][] area;
    private static boolean[][] isVisited;
    private static int N;
    private static int count = 0, number = 0;

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

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

        N = Integer.parseInt(sc.nextLine());

        area = new int[N][N];
        isVisited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String[] nextLine = sc.nextLine().split("");
            for (int j = 0; j < N; j++) {
                area[i][j] = Integer.parseInt(nextLine[j]);
            }
        }
        sc.close();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!isVisited[i][j] && area[i][j] == 1){
                    count = 0;
                    number++;
                    dfs(i,j);
                    list.add(count);
                }
            }
        }

        Collections.sort(list);
        System.out.println(number);
        list.forEach(System.out::println);
    }

    private static void dfs(int x, int y){
        isVisited[x][y] = true;
        count++;
        for (int i = 0; i < dx.length; i++) {
            // 한칸씩 이동
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N || isVisited[nx][ny] || area[nx][ny] != 1) continue;
            isVisited[nx][ny] = true;
            dfs(nx, ny);
        }
    }
}
728x90
반응형