[백준] 2667번 - 단지번호붙이기(JAVA)

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

- 문제 -

---

- 풀이 과정 -

주어진 2차원 배열에서 1로 연속된 개수와 1로 이어진 공간의 개수를 출력하는 문제입니다.

2차원 배열을 순차적으로 탐색하면서 1이 발견되면 연속된 1을 찾기 위한 탐색을 시작합니다.

탐색을 시작하게 되면 상, 하, 좌, 우의 값을 확인하여 해당 값이 1이면 다음 탐색 지점으로 등록하고 0일 경우 패스합니다.

탐색하면서 1이 발견된 경우 카운트를 해주어서 1의 개수를 누적합니다.

이번 문제에서는 bfs알고리즘을 이용하기에 큐를 사용하여 다음 탐색 지점을 큐에 등록합니다.

탐색을 위해 다음 탐색 지점을 등록했으면 다시 방문하지 않기 위해 해당 지점의 값을 1에서 0으로 변경합니다.

그러면 다른 위치에서 동일 지점을 탐색하기 위해 값을 확인하여도 해당 지점은 0으로 변경되었기에 탐색하지 않고 패스할 수 있게 됩니다.

그림에는 탐색 과정이 두 개씩 이동하는 것으로 보이지만 실제로는 큐에서 꺼내어 하나씩 진행합니다.

탐색이 한번 종료될 때마다 총 단지수를 출력하기 위해 탐색 회수를 누적합니다.

또한 누적된 카운트 값을 List에 저장 후 배열을 다시 순차적으로 탐색합니다.

이미 탐색된 지역들은 모두 0이기에 탐색되지 않으며 다음 1의 값이 있는 곳이 탐색되면 이전 순서를 반복하게 됩니다.

모든 탐색이 종료된 되었다면 List에 저장한 값을 정렬 후 총 단지수와 함께 출력하면 됩니다.

---

- 소스 코드(bfs) -

package com.test;
 
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 int[][] map;
    static int n;
    static int sum=0;
    static ArrayList<Integer> list;
    
    //2667번 - 단지번호붙이기
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        list=new ArrayList<Integer>();
        
        n=Integer.parseInt(br.readLine());
        map=new int[n][n];
        int count=0;    //총 단지수
        
        for(int i=0;i<n;i++) {
            String str=br.readLine();
            for(int j=0;j<n;j++) {
                map[i][j]=str.charAt(j)-'0';
            }
        }
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(map[i][j]==1) {  //한번 실행 시 단지 하나
                    bfs(i,j);
                    count++;
                    sum=0;
                }
            }
        }
        Collections.sort(list);
        sb.append(count).append("\n");
        
        for(int i=0;i<list.size();i++) {
            sb.append(list.get(i)).append("\n");
        }
        System.out.println(sb);
    }
    
    public static void bfs(int x,int y) {
        Queue<Node> q=new LinkedList<Node>();
        int[] dx={-1,1,0,0};
        int[] dy= {0,0,-1,1};
        sum+=1;
        map[x][y]=0;
                
        q.offer(new Node(x,y));
        
        while(!q.isEmpty()) {
            Node node=q.poll();
            
            for(int i=0;i<4;i++) {  //상하좌우 1인 값 찾기
                int nx=node.x+dx[i];
                int ny=node.y+dy[i];
                
                if(nx>=0&&nx<n&&ny>=0&&ny<n) {
                    if(map[nx][ny]==1) {
                        q.offer(new Node(nx,ny));
                        map[nx][ny]=0;
                        sum+=1;
                    }
                }
            }   
        }
        list.add(sum);
    }
}
class Node{
    int x;
    int y;
    
    Node(int x,int y) {
        this.x=x;
        this.y=y;
    }
}