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


import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.next());

        Queue q = new LinkedList<>();
        int groupCount = 0;
        List res = new LinkedList<>();
        Node[][] arr = new Node[n][n];
        Node start = null;
        for (int i = 0; i < n; i++) {
            String temp = scan.next();
            for (int j = 0; j < n; j++) {
                int value = temp.charAt(j) - '0';
                arr[i][j] = new Node(i, j, value);
                if (arr[i][j].val == 1) {
                    start = arr[i][j];
                }
            }
        }
        while (start != null) {
            groupCount++;
            int count = 1;
            start.val = -1;
            q.offer(start);

            while (!q.isEmpty()) {
                Node[] aj = find(q.poll(), n, arr);
                for (int i = 0; i < 4; i++) {
                    if (aj[i] != null) {
                        aj[i].val = -groupCount;
                        count++;
                        q.offer(aj[i]);
                    }
                }

            }

//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    System.out.print(arr[i][j].val);
//                }
//                System.out.println();
//            }
            res.add(count);
            // start를 기준으로 탐색시작
            start = null;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr[i][j].val == 1) {
                        start = arr[i][j];
                    }
                }
            }
        }

        System.out.println(groupCount);
        for(int i =0 ; i < groupCount ; i ++) {
            res.sort(null);
            System.out.println(res.get(i));
        }
    }

    static Node[] find(Node node, int n, Node[][] array) {
        Node[] result = new Node[4];
        int[] addCol = { 0, 0, -1, 1 };
        int[] addRow = { -1, 1, 0, 0 };

        for (int i = 0; i < 4; i++) {
            int col = node.col + addCol[i];
            int row = node.row + addRow[i];

            if (col >= n || row >= n || col < 0 || row < 0) {
                result[i] = null;
            } else {
                if (array[col][row].val == 1) {
                    array[col][row].dist = node.dist + 1;
                    result[i] = array[col][row];
                } else {
                    result[i] = null;
                }
            }
        }
        return result;
    }

    static class Node {
        int col;
        int row;
        int val;
        int dist;

        public Node(int col, int row, int val) {
            super();
            this.col = col;
            this.row = row;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node [col=" + col + ", row=" + row + ", val=" + val + ", dist=" + dist + "]";
        }

    }

}

+ Recent posts

"여기"를 클릭하면 광고 제거.