[BOJ] 2667. 단지번호붙이기(BFS, DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

집이 있는곳을 발견하면, 해당 집과 연결된 집들을 모두 방문하면서 단지내 집의 수를 count

여기서 집들을 방문하면서 단지번호를 저장해준다.

#. BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class BOJ2667_bfs {
 
    static int dx[] = { -1, 1, 0, 0 };
    static int dy[] = { 0, 0, -1, 1 };
 
    static public class pos {
        int x;
        int y;
 
        public pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int map[][] = new int[N][N];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
        int mark = 1, cnt;
        Queue<pos> q = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<Integer>();
        // 모든 좌표를 확인하면서
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 집이 있다면
                if (map[i][j] == 1) {
                    cnt = 1;    // 해당 단지내 집의 수를 count하기 위한 변수
                    mark++;        // 단지 번호
                    q.add(new pos(i, j));
                    map[i][j] = mark;
 
                    while (!q.isEmpty()) {
                        pos now = q.poll();
 
                        for (int d = 0; d < 4; d++) {
                            int xx = now.x + dx[d];
                            int yy = now.y + dy[d];
                            // 범위를 벗어나면 pass
                            if (xx < 0 || yy < 0 || xx >= N || yy >= N) continue;
                            // 집이 없거나, 이미 단지가 정해진 집이라면 pass
                            if (map[xx][yy] != 1) continue;
                            // 단지를 정해주고 Queue에 넣기
                            map[xx][yy] = mark;
                            cnt++;
                            q.add(new pos(xx, yy));
                        }
                    }
                    // 단지내 집의 수를 list에 넣어주기
                    res.add(cnt);
                }
            }
        }
        System.out.println(mark - 1);
        // 단지내 집의 수를 오름차순으로 정렬
        res.sort(null);
        for (int x : res) 
            sb.append(Integer.toString(x) + '\n');
        System.out.println(sb);
    }
 
}
 

#. DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class BOJ2667_dfs {
 
    static int dx[] = { -1, 1, 0, 0 };
    static int dy[] = { 0, 0, -1, 1 };
    static int N, cnt, mark = 1;
    static int map[][];
    static ArrayList<Integer> res = new ArrayList<Integer>();
    
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
        // 모든 좌표를 확인하면서
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 집이 있다면
                if (map[i][j] == 1) {
                    cnt = 0;    // 해당 단지내 집의 수를 count하기 위한 변수
                    mark++;        // 단지 번호
                    dfs(i, j);
                    // 단지내 집의 수를 list에 넣어주기
                    res.add(cnt);
                }
            }
        }
        
        System.out.println(mark - 1);
        res.sort(null);
        for (int x : res) 
            sb.append(Integer.toString(x) + '\n');
        System.out.println(sb);
    }
 
    public static void dfs(int x, int y) {
        cnt++;    // 단지내 집의 수를 count
        map[x][y] = mark;    // 단지번호 저장
        // 주변 땅을 확인
        for (int d = 0; d < 4; d++) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            // 범위를 벗어나면 pass
            if (xx < 0 || yy < 0 || xx >= N || yy >= N) continue;
            // 집이 없거나, 이미 단지가 정해진 집이라면 pass
            if (map[xx][yy] != 1) continue;
            // 단지를 정해주고 해당 좌표를 dfs에 넘겨주기
            dfs(xx, yy);
        }
    }
}