[JAVA]백준_2667_단지번호붙이기

문제링크

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

2667번: 단지번호붙이기

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static int N;
	static char map[][];
	static boolean isVisited[][];
	static Queue<Node> q = new LinkedList<>();
	static ArrayList<Integer> list = new ArrayList<>();
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		isVisited = new boolean[N][N];
		
		for(int i=0;i<N;i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(!isVisited[i][j] && map[i][j]=='1') {
					q.offer(new Node(i,j));
					bfs(i,j);
				}
			}
		}
		
		Collections.sort(list);
		System.out.println(list.size());
		for(int i=0;i<list.size();i++) {
			if(list.get(i) == 0) System.out.println("1");
			else System.out.println(list.get(i));
		}
		
	}
	
	static void bfs(int row,int col) {
		int count =0;
		while(!q.isEmpty()) {
			Node n = q.poll();
			for(int d=0;d<4;d++) {
				int nx = n.row + dx[d];
				int ny = n.col + dy[d];
				
				if(nx<0 || nx>=N || ny<0 || ny>=N || isVisited[nx][ny] || map[nx][ny]=='0') continue;
				
				isVisited[nx][ny] = true;
				q.offer(new Node(nx,ny));
				count++;
			}
		}
		list.add(count);
	}
	
	static class Node{
		int row;
		int col;
		public Node(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}
	}
}

 

 

bfs로 문제 해결했다.

아파트 단지 인 곳만 돌면서 (map[nx][ny]=='1') 단지이면 큐에 넣고 아니면 지나가는 식으로 푼 후에

단지가 끝나면? ArrayList에 현재 단지의 크기를 넣어주었다. list.add(count)

 

주의할 점이 아파트 단지의 크기가 1이면 0이 삽입되기 때문에

나중에 답을 출력할 때 if(list.get(i) == 0) System.out.println("1") 을 해주었다.