문제: https://www.acmicpc.net/problem/2667
답을 안보고 풀 수 있을 것이라 생각했는데, 아직 머리속으로 떠올린 것을 구현하는 것이 어렵다.😅

설명

이 문제는 0과 1로 구성된 지도에서 1인 지점들끼리 이룬 군집과 각 군집의 요소의 개수를 찾는 문제이다.
따라서 군집을 찾는 과정과 각 군집의 요소 개수를 세는 과정이 필요하다.
DFS 알고리즘과 BFS 모두 풀이가 가능하다.

DFS 알고리즘

DFS 알고리즘은 특정 노드에서 연결된 가장 깊은 곳까지 들어가 탐색하는 알고리즘이다.
이 풀이 방법은 두번의 재귀 알고리즘을 거친다. 첫번째는 지도에서 1로 구성된 군집을 찾고, 두번째는 이 군집내의 방문 여부를 확인하면서 군집의 요소 개수를 세는 것이다.
군집내 요소들은 동,서,남,북 4방향의 요소들이고, 이 방향들을 모두 방문하는 재귀함수를 작성한다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P2667 {
    static int N;
    static int[][] map;
    static StringTokenizer st;
    static ArrayList<Integer> danjiCount;
    static boolean[][] visit;
    static int count;
	
    // 방문할 4방향 배열
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P2667/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        visit = new boolean[N][N];
        danjiCount = new ArrayList<>();

		// 2차원 map 초기화
        for (int i = 0; i < N; i++) {
            String st = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = st.charAt(j) - '0';
            }
        }
		
        // 2차원 map을 돌면서, 1이고 방문하지 않은 곳이라면
        // 그 지점부터 탐색을 시작한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visit[i][j]) {
                    count = 1;
                    findDanji(i, j);
                    danjiCount.add(count);
                }
            }
        }

        sb.append(danjiCount.size()).append("\n");
        Collections.sort(danjiCount);
        for (int i = 0; i < danjiCount.size(); i++) {
            sb.append(danjiCount.get(i)).append("\n");
        }
        System.out.println(sb);
    }

    private static void findDanji(int x, int y) {
        visit[x][y] = true;
        // 방문한 지점에서 4방향을 모두 탐색한다
        for (int i = 0; i < 4; i++) {
            int x_new = x + dx[i];
            int y_new = y + dy[i];
            if (x_new >= 0 && y_new >= 0 && x_new < N && y_new < N) {
                if (map[x_new][y_new] == 1 && !visit[x_new][y_new]) {
                	// 방문하지 않았고, 1이라면 해당 지점부터 탐색을 시작한다.
                    findDanji(x_new, y_new);
                    count++;
                }
            }
        }
    }
}

BFS 알고리즘

BFS는 같은 레벨에 있는 이웃한 노드들을 모두 확인하면서 탐색하는 로직이다.
큐(Queue) 자료구조를 이용하며, 주어진 좌표값에서 주변의 조건들을 만족하는 좌표를 큐에 넣는다. 순서대로 poll()을 통해 좌표값들을 하나씩 꺼내어 확인해 탐색하고, 큐에 담긴 모든 좌표값을 탐색하면 알고리즘이 종료된다.

온전치 않은 코드이다.

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 + dx[i];
            int y_new = temp.y + dy[i];
            if (x_new >= 0 && y_new >= 0 && x_new < N && y_new < N) {
                if (map[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++;
                }
            }

만약 map에 0이 더 많다면(갔는데 꽝인 경우), BFS가 더 유리할 수도 있겠다.

Reference

• https://incomeplus.tistory.com/408