2667번 : 단지번호붙이기

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

2667번: 단지번호붙이기

 

 

문제

 

 

코드

import java.util.*;

public class Main {
    static int g[][] = new int[25][25];
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); sc.nextLine();

        for(int i=0;i<n;i++) {
            String str = sc.nextLine();
            for(int j=0;j<n;j++) {
                g[i][j] = str.charAt(j) - '0';
            }
        }

        ArrayList<Integer> arr = new ArrayList<>();
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(g[i][j]==1) arr.add(bfs(i, j));
            }
        }
        System.out.println(arr.size());
        Collections.sort(arr);
        for(int i : arr) System.out.println(i);
    }

    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    private static int bfs(int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        int count=0;

        q.add(new int[]{i, j});
        g[i][j]=0;

        while(!q.isEmpty()) {
            int cur[] = q.poll();
            count++;
            i = cur[0]; j = cur[1];
            for(int z=0;z<4;z++) {
                int nx = i+dx[z];
                int ny = j+dy[z];
                if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
                if(g[nx][ny]==1) {
                    q.add(new int[]{nx, ny});
                    g[nx][ny]=0;
                }
            }
        }
        return count;
    }
}

 

 

해결방법

그래프의 탐색 시작 지점을 모르기에 2차원 배열 g를 전부 돌면서 값이 1인 곳에서 bfs()를 호출하였다.

탐색 중 값이 1인 부분은 0으로 바꿔 다시 탐색하지 않게끔 했다.
한 번의 bfs()가 끝나면 더 이상 확장이 불가능하므로 마을 하나가 탄생한다.
bfs()는 단지 내 집의 수(1의 개수)를 반환한다.