[알고리즘_풀이] 백준 2667번, 단지번호 붙이기 ,DFS, BFS

DFS, 재귀

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 지도의 크기를 담은 int 배열
        // 지도는 n x n 이다.
        int n = sc.nextInt();
        sc.nextLine(); // nextInt() 즉, 정수를 입력 받은 후, nextLine()을 써줘야한다.

        // 지도 상, 단지가 있으면 1, 없으면 0
        int[][] dangi = new int[n][n];

        // 방문했는지 체크하는 배열
        // 방문했으면 true, 아직 방문 안했거나 못할 조건이면 false
        boolean[][] visited = new boolean[n][n];


        // 공백 없이 입력 받으므로, 정수 배열에 하나씩 잘라서 담는다.
        String str = "";
        for(int i=0; i<n; i++){
            str = sc.nextLine();
            for(int j=0; j<str.length(); j++){
                dangi[i][j] = (int)str.charAt(j) - 48;
            }
        }

        int count = 0;
        // 하나씩 돌아가면서 dfs로 순회하고, 더 이상 순회할 곳이 없을 때 다시 돌아와서 다른 방문하지 않은 곳에서 새로 시작한다.
        // 단지 수는 dfs를 시행한 개수를 담는다. -> 처음 들어갈 때 카운트하면 된다.
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                // 단지가 1이고, 아직 방문하지 않은 곳에서 깊이우선탐색을 시작한다.
                if(dangi[i][j] == 1 && visited[i][j] == false){
                    count += 1;
                    dfs(i, j, count, n, dangi, visited);
                }
            }
        }

        // 단지의 개수를 출력한다.
        System.out.println(count);

        int[] map_count = new int[count+1];

        for(int[] di : dangi ){
            for(int dj : di){
                if(dj > 0){
                    map_count[dj]++;
                }
            }
        }

        Arrays.sort(map_count);

        for(int i=1; i<map_count.length; i++){
            System.out.println(map_count[i]);
        }

    }

    static void dfs(int i, int j, int count, int n, int[][] dangi, boolean[][] visited){
        // 방문 입구이므로 방문했다(false -> true)고 표시 한다.
        visited[i][j] = true;
        // count는 dfs를 시작할 때마다 숫자가 1씩 증가하고, 한번 탐색할 때는 끝날 떄까지 마치 '단지'번호 같이 다 같은 count값을 가진다.
        dangi[i][j] = count;

        // 오른쪽, 왼쪽, 위, 아래순으로 순회한다.
        // 현재 : (0,0)
        // 왼쪽 : (0, -1), 오른쪽 : (0, 1), 위(-1, 0), 아래(1, 0)
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};

        for(int k=0; k<4; k++){
            // 여기서 x는 행을 의미하고, y는 열을 의미한다. 일반적인 (x, y)값과는 다르다.
            int x = i+dx[k];
            int y = j+dy[k];

            // 상하좌우를 검사할 때, 배열의 범위를 벗어나면 안되므로 체크하고 들어간다.
            // x(행) : 0 <= x < n
            // y(열) : 0 <= y < n
            if(x>=0 && x<n && y>=0 && y<n){
                if(!visited[x][y] && dangi[x][y]>0){
                    dfs(x, y, count, n, dangi, visited);
                }
            }
        }
    }
}

 

DFS, 스택

import java.util.*;

// 단지번호 붙이기 (플러드필), dfs, Stack
// https://www.acmicpc.net/problem/2667
public class Main {
    static Stack<Node> stack = new Stack<>();
    // 재귀는 자식을 검사할 때, 자기자신을 또 호출하는데,
    // 현재 스택에 자식을 넣는 과정을 통해서 자식을 하나씩 확인할 수 있다.
    public static int dfs(boolean[][] visited, int[][] dangi, int countNum, int N) {
        // 오른쪽, 왼쪽, 위, 아래순으로 순회한다.
        // 현재 : (0,0)
        // 왼쪽 : (0, -1), 오른쪽 : (0, 1), 위(-1, 0), 아래(1, 0)
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        // 부모를 꺼내고 검사하면서 자식을 상하좌우로 확인하고 또 넣고, ... 반복
        // 결과적으로 부모의 자식, 또 부모의 자식, ..., 을 통해서 깊이 우선 탐색을 할 수 있다.
        while(!stack.isEmpty()){
            Node out = stack.pop();
            dangi[out.x][out.y] = out.count;
            visited[out.x][out.y] = true;
            countNum += 1;

            for(int k=0; k<4; k++){
                int x = out.x + dx[k]; // 행
                int y = out.y + dy[k]; // 열
                // 상하좌우를 검사할 때, 배열의 범위를 벗어나면 안되므로 체크하고 들어간다.
                // x(행) : 0 <= x < n
                // y(열) : 0 <= y < n
                if(x>=0 && y>=0 && x<N&& y<N) {
                    if(visited[x][y] == false && dangi[x][y] == 1){
                        //visited[x][y] = true;
                        stack.add(new Node(x, y, out.count));
                    }
                }
            }
        }

        // 재귀호출을 하지 않았기 떄문에
        // 이 함수가 return 된다는 것은 끝났다는 것.
        // 계속 카운트 해왔던 단지의 수를 반환할 수 있다.
        return countNum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 지도의 크기를 담은 int 배열
        // 지도는 n x n 이다.
        int N = sc.nextInt();
        sc.nextLine();

        //
        int[][] dangi = new int[N][N];
        boolean[][] visited  = new boolean[N][N];

        for(int i=0; i<N; i++){
            String str = sc.nextLine();
            for(int j=0; j<N; j++){
                dangi[i][j] = str.charAt(j) - 48;
            }
        }

        int count = 0;
        // 각각 단지의 개수를 담은 List
        List<Integer> dangiNum = new ArrayList<>();
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(visited[i][j] == false && dangi[i][j] == 1) {
                    count++;
                    stack.add(new Node(i, j, count));
                    int tmp = dfs(visited, dangi, 0, N);
                    dangiNum.add(tmp);
                }
            }
        }

        System.out.println(dangiNum.size());
        Collections.sort(dangiNum);
        for(int i=0; i<dangiNum.size(); i++){
            System.out.println(dangiNum.get(i));
        }

    }

    static class Node{
        int x;
        int y;
        int count;
        public Node(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

 

BFS, 큐

import java.util.*;

// 단지번호 붙이기 (플러드필), bfs, Queue
// https://www.acmicpc.net/problem/2667
public class Main {
    static Queue<Node> q = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 지도의 크기를 담은 int 배열
        // 지도는 n x n 이다.
        int N = sc.nextInt();
        sc.nextLine();

        // 지도 상, 단지가 있으면 1, 없으면 0
        int[][] dangi = new int[N][N];

        // 방문했는지 체크하는 배열
        // 방문했으면 true, 아직 방문 안했거나 못할 조건이면 false
        boolean[][] visited  = new boolean[N][N];


        // 공백 없이 입력 받으므로, 정수 배열에 하나씩 잘라서 담는다.
        for(int i=0; i<N; i++){
            String str = sc.nextLine();
            for(int j=0; j<N; j++){
                dangi[i][j] = str.charAt(j) - 48;
            }
        }

        for(int i=0; i<dangi.length; i++){
            String str = sc.nextLine();
            for(int j=0; j<str.length(); j++){
                dangi[i][j] = str.charAt(j) - 48;
            }
        }

        int count = 0;
        List<Integer> dangiNum = new ArrayList<>();
        for(int i=0; i<dangi.length; i++){
            for(int j=0; j<dangi[0].length; j++){
                if(visited[i][j] == false && dangi[i][j] == 1) {
                    count++;
                    q.add(new Node(i, j, count));
                    visited[i][j] = true;
                    int tmp = bfs(visited, dangi, 0);
                    dangiNum.add(tmp);
                }
            }
        }

        System.out.println(dangiNum.size());
        Collections.sort(dangiNum);
        for(int i=0; i<dangiNum.size(); i++){
            System.out.println(dangiNum.get(i));
        }
    }

    public static int bfs(boolean[][] visited, int[][] dangi, int countNum) {
        // 오른쪽, 왼쪽, 위, 아래순으로 순회한다.
        // 현재 : (0,0)
        // 왼쪽 : (0, -1), 오른쪽 : (0, 1), 위(-1, 0), 아래(1, 0)
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        while(!q.isEmpty()){
            Node out = q.poll();
            dangi[out.x][out.y] = out.count;
            visited[out.x][out.y] = true;
            countNum += 1;

            for(int k=0; k<4; k++){
                int x = out.x + dx[k];
                int y = out.y + dy[k];
                if(x>=0 && y>=0 && x<dangi.length && y<dangi[0].length) {
                    if(visited[x][y] == false && dangi[x][y] == 1){
                        q.add(new Node(x, y, out.count));
                    }
                }
            }
        }

        return countNum;
    }

    static class Node{
        int x;
        int y;
        int count;
        
        public Node(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

 

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

2667번: 단지번호붙이기