일단 시작해보는 블로그

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

CS/알고리즘 풀이

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

Selina Park 2019. 9. 17. 20:00

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번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수

www.acmicpc.net

 

Comments