백준 2667_단지번호붙이기_JAVA

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

2667번: 단지번호붙이기

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] grid;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static LinkedList<Integer> answer = new LinkedList<>();
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 가로,세로 길이
        grid = new int[N][N];
        visited = new boolean[N][N];

        StringReader st;

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                grid[i][j] = str.charAt(j) - '0'; // char -> int로 형변환!
            }
        }

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

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

    private static void dfs(int x, int y) {
        count++;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny] && grid[nx][ny] == 1) {
                visited[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }
}

 

회고

- 예전에 Swift로 풀었던 기억이 나는 문제다.

- 기본적인 DFS문제여서 쉽게 풀었다.

 

BFS 풀이

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] grid;
    static boolean[][] visited;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int houseCount = 0;
    static ArrayList<Integer> answerList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        grid = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                grid[i][j] = line.charAt(j) - '0';
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    answerList.add(BFS(i, j, 1));
                    houseCount++;
                }
            }
        }
        Collections.sort(answerList);
        System.out.println(houseCount);
        for(int i: answerList) {
            System.out.println(i);
        }
    }


    public static int BFS(int x, int y, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y, c});
        int count = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cc = cur[2];
            count++;

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                int nc = cc + 1;
                if (nx >= 0 && ny >= 0 && nx < N && ny < N && grid[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, nc});
                }
            }
        }
        return count;
    }
}