백준_2667번_단지번호붙이기(자바)

 

백준_2667번_단지번호붙이기(자바)

 

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

2667번: 단지번호붙이기

 

이번 문제는 BFS/DFS로 모두 풀 수 있는 문제이며, 저는 BFS로 풀이하였습니다.

[ DFS 풀이 법도 추가하였습니다. ] 

 

최초 풀이시에 틀릴리가 없는데 틀려서 뭐지? 하고 문제를 다시 읽어보니, 문제 아랫 부분에 " 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오." 이런 문구가 있더군요, 문제를 잘 읽읍시다!

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n;
    static int[][] map;
    static boolean[][] chx;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int result;
    static int size;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n= Integer.parseInt(st.nextToken());
        map = new int[n][n];
        chx = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            for (int j = 0; j < n; j++) {
                map[i][j] = s.charAt(j)-'0';
            }
        }

        result=0;
        List<Integer> sizes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                size = 0;
                if (map[i][j] == 1 && chx[i][j] == false){
                    result++;
                    chx[i][j]=true;
                    bfs(i,j);
//                    dfs(i,j);
                    sizes.add(size);
                }
            }
        }

        Collections.sort(sizes);
        System.out.println(result);
        for (int a : sizes) {
            System.out.println(a);
        }

    }

    private static void dfs(int x, int y) {
        chx[x][y] =true;
        size += 1;

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

            if(nextX < 0 || nextY <0 || nextX >= n || nextY >= n || map[nextX][nextY]==0||chx[nextX][nextY]){
             continue;
            }
            dfs(nextX,nextY);

        }
    }

    private static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});

        while (!q.isEmpty()){
            size+=1;
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int nextX = nowX+dx[i];
                int nextY = nowY+dy[i];

                if(nextX < 0 || nextY <0 || nextX >= n || nextY >= n || map[nextX][nextY]==0||chx[nextX][nextY]) continue;

                q.add(new int[]{nextX,nextY});
                chx[nextX][nextY] = true;
            }
        }
    }

}