BFS 마법의 비료

<hide/>
/*

5 4
1 1 1 1 0
0 0 0 1 1 
1 1 0 0 0 
0 0 0 0 1
 
 */
 package first;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class MagiFertilizer0 {

	static int MAX_COUNT = 101;
	static int [][] AdjMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int [][] VisitMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int Width; 
	static int Height;
	static int DIRECTION = 4;
	static int [][] DirMatrix = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<Integer> queueRow = new LinkedList<>();
	static Queue<Integer> queueCol = new LinkedList<>();
	static double res = 0.0000;
	static int Area = 0;
	static int[] AreaArray = new int[MAX_COUNT];
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		Width = scan.nextInt();
		Height = scan.nextInt();
		
		for(int i = 1; i <= Height; ++i) {
			for(int j = 1; j<= Width; ++j) {
				AdjMatrix[i][j] = scan.nextInt();
			}
		}
		
		for(int i = 1; i <= Height; ++i) {
			for(int j = 1; j<= Width; ++j) {
				if(1 == AdjMatrix[i][j] && 0 == VisitMatrix[i][j]) {
					++Area;
					BFSmethod(i, j);	
				}
			}
		}
		
		for(int i = 1; i <= Area; ++i) {
			res +=  Math.sqrt((double)AreaArray[i]);
			System.out.printf("AreaArray[%d] = %d, res = %f\n", i, AreaArray[i], (double) res);
		
		}
		System.out.println(res);
	}
	
	public static void BFSmethod(int _StartRow, int _StartCol) {
		
		VisitMatrix[_StartRow][_StartCol] = 1;
		queueRow.offer(_StartRow);
		queueCol.offer(_StartCol);
		++AreaArray[Area];
		
		while(false == queueRow.isEmpty()) {
			
			int currRow =  queueRow.poll();
			int currCol = queueCol.poll();
			for(int i = 0; i < DIRECTION; ++i) {
				int nextRow = currRow + DirMatrix[i][0];
				int nextCol = currCol + DirMatrix[i][1];
				if(1 == VisitMatrix[nextRow][nextCol]) continue;
				if(1 == AdjMatrix[nextRow][nextCol]
				&& 1 <= nextRow && nextRow <= Height
				&& 1<= nextCol  && nextCol <= Width) {
					VisitMatrix[nextRow][nextCol] = 1;
					queueRow.offer(nextRow);
					queueCol.offer(nextCol);
					++AreaArray[Area];
				}
			}
		}
	}
}

  - AreaArray 배열과 Area를 만든다.

  - 메인 함수에서 bfs를 실행하기 전에  Area를 증가시킨다.

  - BFSmethod 에서 while문의 바로 전과 while문 마지막에 AreaArray[Area]를 증가시킨다. 

  - 마지막으로 저장된 배열의 요소들을 res에 누적해서 더해준다.

 

 

  Note) 입출력 예시

<hide/>
[입력]
5 4
1 1 1 1 0
0 0 0 1 1 
1 1 0 0 0 
0 0 0 0 1

[출력]
AreaArray[1] = 6, res = 2.449490
AreaArray[2] = 2, res = 3.863703
AreaArray[3] = 1, res = 4.863703
4.863703305156273