이것저것 개발 블로그

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main_BJ_2667_단지번호붙이기 {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int cnt, house, n;
    static PriorityQueue<Integer> houses = new PriorityQueue<>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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] = str.charAt(j) - '0';
            }
        }

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

        System.out.println(cnt);
        int size = houses.size();
        for(int i=0; i<size; i++)
            System.out.println(houses.poll());
    }//main
    private static void dfs(int x, int y){
        visited[x][y] = true;

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

            if(check(nx, ny) && !visited[nx][ny] && map[nx][ny] != 0){
                house++;
                dfs(nx, ny);
            }
        }

    }//dfs

    private static boolean check(int x, int y){
        if(x<0 || y<0 || x>=n || y>=n)
            return false;
        return true;
    }//check
}

완탐으로 가면 좋을것 같아서 시작했다.

dfs, bfs어느것도 상관이 없을 것 같지만 최근에 bfs로 문제를 많이 풀어본 것 같아서 dfs를 이용해서 해봤다.

전체 단지 수 변수를 만들고, 해당 단지를 오름차순으로 저장하기 위해 Priority Queue를 사용해서 풀었다.

그런데,, 마지막 출력할때 queue를 poll하면 사이즈 줄어들어서 모두 출력 안되는 사실을 자꾸 까먹어서 웨않되를 자꾸 외치는 바보...

그래프 문제를 풀어보기에 간단하고 괜찮은 문제~~