백준 2667번 단지 번호붙이기 자바

문제 링크

풀이

기존에 풀었던 경로문제와 숫자세기를 사용한 복합적인 문제이다 큐를 사용해 dfs를 구현했으며 독립된 단지를 모두 탐색하기 위하여 매트릭스를 모두 탐색하였다. 문제를 겪었던 내용은 인접 매트릭스를 채워넣을 때 평소처럼 nextInt()만을 사용해서 한 줄에 있는 요소들을 하나의 정수로 입력했던 것이다. next()메서드와 chartAt()메서드를 사용하여 인접 메트릭스를 만들었고, PriorityQueue를 통해 최소값을 빠르게 뱉어내도록 구현했다.

코드

import java.util.*;

public class Main{


    static int[][] map;
    static boolean[][] visit;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,-1,0,1};
    static PriorityQueue<Integer> heap;
    static int count = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        map = new int[n+2][n+2];
        visit = new boolean[n+2][n+2];
       
        heap = new PriorityQueue<>();
        for(int i = 1; i<=n;i++){
        	String s =sc.next();
            for(int j=1; j<=n;j++){
                map[i][j]=s.charAt(j-1)-'0';
            }
        }
        for(int i = 1 ; i<=n;i++){
            for(int j = 1 ; j<=n;j++){
                if(!visit[i][j]&&map[i][j]==1){
                    bfs(i,j);
                }
            }
        }
        System.out.println(heap.size());
        while(!heap.isEmpty()){
            System.out.println(heap.poll());
        }
    }
    
    static void bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        int[] arr = {x,y};
        q.offer(arr);
        count++;
        visit[x][y]=true;
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            for(int i=0; i<4;i++){
                if(map[tmp[0]+dx[i]][tmp[1]+dy[i]]==1&&!visit[tmp[0]+dx[i]][tmp[1]+dy[i]]){
                	int[] arr2 = {tmp[0]+dx[i],tmp[1]+dy[i]};
                   q.offer(arr2);
                   count++;
                   visit[tmp[0]+dx[i]][tmp[1]+dy[i]]=true;
                }

            }

        }
        heap.offer(count);
        count=0;
    }
}