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

---

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

---

🔍 문제 풀이

문제 도식화

이 문제에서 visited는 안 써도 되지만, 원본을 유지하기 위해 따로 쓰는 게 좋다.

💻 코드

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static int[][] v;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int n;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n][n];
        for(int i=0; i<n; i++){
            String line = br.readLine();
            for(int j=0; j<n; j++){
                arr[i][j] = line.charAt(j) - '0';

            }
        }

        List<Integer> list = new ArrayList<>();
        v = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(arr[i][j] == 1 && v[i][j] == 0){
                    list.add(bfs(i, j));
                }
            }
        }

        Collections.sort(list);
        System.out.println(list.size());

        for(int val:list){
            System.out.println(val);
        }
    }

    static int bfs(int sx, int sy){
        // 1. 초기화
        Deque<int[]> dq = new ArrayDeque<>();
        int cnt = 1;

        // 2. 초기값
        dq.offer(new int[]{sx, sy});
        v[sx][sy] = 1;

        // 3. 탐색
        while(!dq.isEmpty()){
            int cur[] = dq.poll();
            int cx = cur[0];
            int cy = cur[1];

            // 3.1 4방향, nx와 ny 범위
            for(int d=0; d<4; d++){
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

                // 3.2 미방문 && 이동칸
                if(arr[nx][ny] == 1 && v[nx][ny] == 0){
                    v[nx][ny] = 1;
                    cnt ++;
                    dq.offer(new int[]{nx, ny});
                }
            }
        }
        return cnt;
    }
}

스켈레톤 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static int[][] v;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int n;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n][n];
        for(int i=0; i<n; i++){
            String line = br.readLine();
            for(int j=0; j<n; j++){
                arr[i][j] = line.charAt(j) - '0';

            }
        }



    }

    static int bfs(int sx, int sy){


    }
}