[백준] 2667번

 DFS를 통해 문제를 해결했다. 문제에 집의 수를 오름차순으로 정렬하라는 문구를 보지 않아서 인텔리제이로 코드를 실행하면 성공했지만 제출하니까 틀렸다고 나왔었다.

 문제를 꼼꼼히 확인하자..!

 

 

public class Main {

    static int N, count;
    static int[][] map;
    static boolean[][] visited;
    static List<Integer> list = new ArrayList<>();
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};

    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());   // 지도의 크기 N x N
        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();

            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }

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

        Collections.sort(list);
        System.out.println(list.size());
        for (int i : list) {
            System.out.println(i);
        }
    }

    private static void dfs(int i, int j) {
        visited[i][j] = true;
        int x, y = 0;

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

            if (x >= 0 && y >= 0 && x < N && y < N) {
                if (map[x][y] == 1 && !visited[x][y]) {

                    dfs(x, y);
                    count++;
                }
            }
        }
    }
}