백준 2667 자바 JAVA 단지 번호 붙이기 알고리즘

 

 

백준 2667 단지번호붙이기 문제는 DFS/BFS 하위 문제다. 0과 1로 구성된 맵에서 1인 지점을 찾아서 군집의 갯수와 군집내 요소들의 갯수를 파악하는 문제다. 풀이는 스택+재귀함수를 이용한 DFS와 큐를 이용한 BFS로 풀어볼 수 있다.

 

 

DFS와 BFS 알고리즘을 먼저 이해해야 풀 수 있는 문제다.

백준 1260 DFS와 BFS 알고리즘 자바 JAVA

 

백준 2667 단지 번호 붙이기 알고리즘 문제

 

백준 2667 단지 번호 붙이기 알고리즘 문제

 

DFS 알고리즘

 

먼저 스택과 재귀함수를 이용한 DFS를 통한 방법은 2개의 순회과정을 거친다. 첫번째 순회에서는 1을 찾아서 군집을 찾아내는 과정과 두번째 순회로 들어가서 1과 방문여부를 체크하여 군집 내의 요소들의 갯수를 카운팅하는 로직이다. 군집내의 요소들을 결정하는 요소는 상,하,좌,우에 붙어 있는 요소들이기 때문에 좌표값을 조정해주면서 재귀함수가 진행된다.

 

스택구조로 진행되는 재귀함수 로직의 가장 깊은 곳 까지 들어가서 더 이상 1을 찾을 수 없으면 순차적으로 스택 값들을 반환하면서 군집내의 요소들이 카운팅 된다.

 

JAVA CODE + DFS

/*
    Owner : Developer Blog
    Title : 단지번호붙이기(백준 2667)
    Algorithm : DFS/BFS 알고리즘
    Date : 2022-03-04
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class A_2667 {
    public static int N;
    public static int[][] matrix;
    public static boolean[][] visit;
    public static ArrayList<Integer> counter;
    public static int count;
    public static int[] X_move = {1, -1, 0, 0};
    public static int[] Y_move = {0, 0, -1, 1};
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        matrix =  new int[N][N];
        visit = new boolean[N][N];
        counter = new ArrayList<>();

        for(int i=0; i<N; i++){
            String input = in.next();
            for(int j=0; j<N; j++){
                matrix[i][j] = input.charAt(j)-'0';
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(matrix[i][j]==1 && !visit[i][j]){
                    count=1;
                    recur(i,j);
                    counter.add(count);
                }
            }
        }
        Collections.sort(counter);
        System.out.println(counter.size());
        for(int num:counter) System.out.println(num);
    }
    
    public static void recur(int x, int y){
        visit[x][y] = true;
        for(int i=0; i<4; i++){
            int x_new = x+X_move[i];
            int y_new = y+Y_move[i];
            if(x_new>=0 && y_new>=0 && x_new<N && y_new<N){
                if(matrix[x_new][y_new]==1 && !visit[x_new][y_new]){
                    
                    recur(x_new, y_new);
                    count++;
                }
            }
        }
    }
}

 

 

BFS 알고리즘

DFS가 현재 좌표를 이동하면서 조건에 충족하지 않는 좌표를 만날 때 까지 깊숙하게 들어가는 알고리즘이라면, BFS는 좌표값을 쉽게 이동하지 않는다. 재귀함수를 작동시키는 스택(Stack)이 아니라 큐(Queue) 자료구조를 이용하기 때문이다. 먼저 처음 주어진 좌표값에서 주변의 조건값을 만족하는 좌표들을 큐에 삽입한다.

 

큐의 좌표들을 FIFO 순서로 poll() 하면서 조건값에 맞는 좌표들을 하나씩 찾아나선다. 큐 내의 모든 좌표가 poll() 되면 BFS 알고리즘은 return 하게 된다.

 

큐에 좌표값을 넣기 위해서는 Point 클래스를 사용한다. java >> awt 패키지에 들어있는 Point 클래스는 int(기본타입) 형으로 x,y좌표값을 담을 수 있다. Point 클래스의 멤버 변수 x, y를 통해 큐에 좌표값을 추가하고 출력하면서 로직을 구성할 수 있게 되는 것이다.

백준 2667 단지 번호 붙이기 Point 클래스

 

 

JAVA CODE + BFS

/*
    Owner : Developer Blog
    Title : 단지번호붙이기(백준 2667)
    Algorithm : DFS/BFS 알고리즘
    Date : 2022-03-04
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.awt.Point;

public class A_2667 {
    public static int N;
    public static int[][] matrix;
    public static boolean[][] visit;
    public static Queue<Point> queue;
    public static ArrayList<Integer> counter;
    public static int count;
    public static int[] X_move = {1, -1, 0, 0};
    public static int[] Y_move = {0, 0, -1, 1};
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        matrix =  new int[N][N];
        visit = new boolean[N][N];
        counter = new ArrayList<>();

        for(int i=0; i<N; i++){
            String input = in.next();
            for(int j=0; j<N; j++){
                matrix[i][j] = input.charAt(j)-'0';
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(matrix[i][j]==1 && !visit[i][j]){
                    count=1;
                    bfs(i,j);
                    counter.add(count);
                }
            }
        }
        Collections.sort(counter);
        System.out.println(counter.size());
        for(int num:counter) System.out.println(num);
    }
    // BFS
    public static void bfs(int x, int y){
        queue = new LinkedList<>();
        queue.add(new Point(x,y));
        visit[x][y] = true;

        while(!queue.isEmpty()){
            Point temp = queue.poll();
            for(int i=0; i<4; i++){
                int x_new = temp.x+X_move[i];
                int y_new = temp.y+Y_move[i];
                if(x_new>=0 && y_new>=0 && x_new<N && y_new<N){
                    if(matrix[x_new][y_new]==1 && !visit[x_new][y_new]){
                        queue.add(new Point(x_new, y_new));
                        visit[x_new][y_new]=true;
                        count++;
                    }
                }
            }
        }
    }
    
    // DFS
    public static void dfs(int x, int y){
        visit[x][y] = true;
        for(int i=0; i<4; i++){
            int x_new = x+X_move[i];
            int y_new = y+Y_move[i];
            if(x_new>=0 && y_new>=0 && x_new<N && y_new<N){
                if(matrix[x_new][y_new]==1 && !visit[x_new][y_new]){
                    
                    dfs(x_new, y_new);
                    count++;
                }
            }
        }
    }
}

 

DFS / BFS 결과 비교

DFS와 BFS 알고리즘을 비교해보면 백준 2667 문제에서는 DFS가 더 빠르게 출력되고 있다. 아마 유효한 좌표값이 생각보다 빠르게 발견되서 다음 결과가 나온것으로 보인다. 하지만 1보다 0이 더 많은 상황이라면 노드의 깊이가 길어질 수록 DFS 알고리즘의 성능은 훨씬 떨어지게 된다.

백준 2667 단지 번호 붙이기 알고리즘 문제 결과

 

 

더 많은 알고리즘

 

백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바

백준 1780 종이의 개수 알고리즘 자바 JAVA

백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘 리뷰