JAVA [Algorithm] - 백준 2667 단지번호 붙이기

 

📝문제 설명

 

- map에서 1인 경우에 DFS, BFS가 몇번 실행되는지,

- DFS, BFS 실행되는 경우 그 안에서 몇번 실행되는지 묻는 문제이다.

---

📢입출력 예시

 

---

✏️문제 풀이

DFS 풀이

package Baekjoon.Graph.DFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Baek2667 {

    static int[][] map;
    static boolean[][] visited;
    static ArrayList<Integer> countList = new ArrayList<>();
    static int[] dx = { -1 , 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, count;
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bufferedReader.readLine());

        map = new int[N][N];
        visited = new boolean[N][N];

        for(int i=0; i<N;i++){
            String str = bufferedReader.readLine();
            for(int j=0; j<N; j++){
                char c = str.charAt(j);
                map[i][j] = c - '0';
            }
        }

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

        Collections.sort(countList);

        System.out.println(countList.size());

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

    private static void DFS(int x, int y){
        visited[x][y] = true;
        count++;

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

            if(newX >= 0 && newY >= 0 && newX < N && newY < N){
                if(map[newX][newY] == 1 && !visited[newX][newY]){
                    DFS(newX, newY);
                }
            }
        }
    }
}

 

BFS 풀이

package Baekjoon.Graph.BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Baek2667 {

    static int[][] map;
    static boolean[][] visited;
    static ArrayList<Integer> countList = new ArrayList<>();
    static int[] dx = { -1 , 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, count;
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bufferedReader.readLine());

        map = new int[N][N];
        visited = new boolean[N][N];

        for(int i=0; i<N;i++){
            String str = bufferedReader.readLine();
            for(int j=0; j<N; j++){
                char c = str.charAt(j);
                map[i][j] = c - '0';
            }
        }

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

        Collections.sort(countList);

        System.out.println(countList.size());

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

    private static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x,y});
        visited[x][y] = true;

        count = 0;

        while(!queue.isEmpty()){
            int[] node = queue.poll();
            int currentX = node[0];
            int currentY = node[1];
            count++;

            for(int i=0; i<4; i++){
                int newX = currentX + dx[i];
                int newY = currentY + dy[i];

                if(newX >=0 && newY >= 0 && newX<N && newY<N){
                    if(map[newX][newY] == 1 && !visited[newX][newY]){
                        queue.offer(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
        }
    }
}

---

💡새로 알게된 점

배열의 크기를 알 수 없거나 순서를 보장하고 싶으면 ArrayList에 담아보자!!

---