[백준] 2667 : 단지번호붙이기 (JAVA/자바)

문제

BOJ 2667 : 단지번호붙이기 - https://www.acmicpc.net/problem/2667

풀이

모든 칸을 확인하는데, 집이 있으나 단지 번호가 아직 부여되지 않은 경우(==값은 1이고 visited되지 않은 경우) BFS탐색으로 인접한 집들에 단지 번호를 부여한다. 더 이상 주변에 인접한 집이 없으면 BFS가 종료되고, 탐색 시 카운트 한 집의 개수를 ArrayList에 넣은 후 소팅하여 출력했다.

코드

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 Main {

    static ArrayList<Integer> arr;
    static int[][] map;
    static boolean[][] visited;
    static int n;

    static class Loc{
        int i;
        int j;

        public Loc(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

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

        for (int i = 0; i < n; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(tmp.charAt(j)));
                if(map[i][j]==0){
                    visited[i][j] = true;
                }
            }
        }

        arr = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(!visited[i][j]){
                    bfs(i, j);
                }
            }
        }

        Collections.sort(arr);

        System.out.println(arr.size());
        for (int a : arr) {
            System.out.println(a);
        }

    }

    public static void bfs(int i, int j){

        int[] mi = {0, 0, -1, 1};
        int[] mj = {1, -1, 0, 0};

        Queue<Loc> q = new LinkedList<>();

        q.add(new Loc(i, j));
        visited[i][j] = true;
        int cnt = 0;

        while (!q.isEmpty()) {

            Loc now = q.poll();
            cnt++;

            for (int d = 0; d < 4; d++) { // 상하좌우 인접한 집이 있는지 확인
                int ni = now.i + mi[d];
                int nj = now.j + mj[d];

                if (ni < 0 || nj < 0 || ni >= n || nj >= n) continue;

                if (!visited[ni][nj]) {
                    visited[ni][nj] = true;
                    q.add(new Loc(ni, nj));
                }
            }

        }
        arr.add(cnt);
    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

• 시작점의 visited 처리를 안해줘서 헤맸던 문제 ^^... 시작점을 잊지말자,,,메모,,,

참고 사이트

딱히 없음