[백준 2667, Java] 단지번호 붙이기

문제

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

풀이 

 map을 순회하면서 칸이 비어있으면 넘어가고, 집인 경우 탐색을 한다. 한번 탐색을 할 때 방문처리를 한 것이 다음 탐색에도 쓰이기 때문에 그 칸을 다시 탐색하는 경우는 없다. 따라서 bfs로도 풀 수 있고, dfs로도 풀 수 있다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

/*
  목표 : 단지의 수, 각 단지에 속하는 집의 수
  함수를 한번 호출할 때 방문처리를한 칸의 경우 방문 해제를 하지 않기때문에 dfs/bfs의 시간복잡도는 O(N*N + N+N)으로 같다

 */
public class Main {
    public static int N;
    public static int[][] map;
    public static boolean[][] visited;
    public static final int HOUSE  = 1;
    public static final int EMPTY = 0;

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

    public static ArrayList<Integer> sizeOfEachAres;
    public static int numberOfArea = 0;

    public static class Point{
        int x, y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] line = null;

        N  = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        sizeOfEachAres = new ArrayList<>();

        for(int r= 0; r<N; r++){
            line = br.readLine().split("");
            for(int c=0; c<N; c++){
                map[r][c] = Integer.parseInt(line[c]);
            }
        }

        for(int r = 0; r<N; r++){
            for(int c = 0; c<N; c++){
                if(map[r][c] == HOUSE && !visited[r][c]){
                    int count = getSizeOfAreaByBfs(r,c);
                    sizeOfEachAres.add(count);
                    ++ numberOfArea;
                }
            }
        }

        Collections.sort(sizeOfEachAres);
        bw.write(String.valueOf(numberOfArea)+"\n");
        for(int size : sizeOfEachAres){
            bw.write(String.valueOf(size)+"\n");
        }
        bw.flush();

    }

    //(x,y)를 포함한 단지의 크기
    // (x,y)가 단지 인경우 1 + 주변 셀의 크기
    public static int getSizeOfAreaByDfs(int x, int y){
        if(x<0 || y<0 || x>=N || y>=N){
            return 0;
        }
        else if(visited[x][y]){
            return 0;
        }
        else if(map[x][y] ==EMPTY){
            return 0;
        }
        else{
            visited[x][y] = true;
            int count =1;

            for(int d = 0 ;d<4 ;d++){
               int nx = x + dx[d];
               int ny = y + dy[d];

               count += getSizeOfAreaByDfs(nx, ny);
            }

            return count;
        }
    }

    public static int getSizeOfAreaByBfs(int x, int y){
        int size = 0;
        Queue<Point> queue = new LinkedList<>();

        visited[x][y] = true;
        Point currentHouse = new Point(x, y);
        queue.add(currentHouse);

        while(!queue.isEmpty()){
            currentHouse = queue.poll();
            ++size;

            for(int d = 0; d<4; d++){
                int nx = currentHouse.x + dx[d];
                int ny = currentHouse.y + dy[d];

                if(nx>=0 && ny>=0 && nx<N && ny<N){
                    if(!visited[nx][ny] && map[nx][ny]==HOUSE){
                        Point nextHouse = new Point(nx, ny);
                        visited[nx][ny] = true;
                        queue.add(nextHouse);
                    }
                }
            }
        }
        return size;
    }
}