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

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

2667번: 단지번호붙이기

---

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 28단계

 

DFS와 BFS의 카테고리에 포함되어 있는 문제이다.

 

BFS로 풀었으며 DFS로도 한번 풀어봐야겠다.

 

import java.util.Scanner;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;

public class Question_2667 {

	static ArrayList<Integer> result = new ArrayList<Integer>();
	static int dx[] = { 0, 1, 0, -1};
	static int dy[] = { 1, 0, -1, 0};
	public static int n;
	public static int map[][];
	public static boolean visit[][];

	public static int bfs(int x, int y) {
		Queue<Integer> qx = new LinkedList<Integer>();
		Queue<Integer> qy = new LinkedList<Integer>();
		int result = 0;
		
		qx.add(x);
		qy.add(y);
		
		while(!qx.isEmpty() && !qy.isEmpty()) {
			x = qx.poll();
			y = qy.poll();
			visit[x][y] = true;
			
			for(int i = 0; i < 4; i++) {
				int _x = x + dx[i];
				int _y = y + dy[i];
				if(_x >= 0 && _y >= 0 && _x < n && _y < n) {
					if(map[_x][_y] == 1 && visit[_x][_y] == false) {
						qx.add(_x);
						qy.add(_y);
						visit[_x][_y] = true;
						result++;
					}
				}
			}
		}
		
		return ++result; 
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int count = 0;
		n = sc.nextInt();
		
		map = new int[n][n];
		visit = new boolean[n][n];
		
		for(int i = 0; i < n; i++) {
			String temp = sc.next();
			for(int j = 0; j < n; j++) {
				map[i][j] = temp.charAt(j) - 48;
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(map[i][j] == 1 && visit[i][j] == false) {
					result.add(bfs(i, j));
					count++;
				}
			}
		}
		
		Collections.sort(result);
		
		System.out.println(count);
		
		for(int i : result) {
			System.out.println(i);
		}
		
	}
}