[JAVA] NHN 모의시험 문제

 

---

 

• 코드

정답 코드 : 행렬이 뭉쳐있는 묶음 수와 묶음 덩어리의 개수를 파악하는 문제이다.

               FOR문을 통해 첫번째 묶음의 위치를 알아내면 BFS로 근처에있는 1의 개수를 모두 더 해준 다음 return해주는 방식을 사용하였다.

 

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

class Main {
	static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};
	static boolean[][] check;
	
  private static void solution(int sizeOfMatrix, int[][] matrix) {
    // TODO: 이곳에 코드를 작성하세요.
		check = new boolean[sizeOfMatrix][sizeOfMatrix];
		int count = 0;
		ArrayList<Integer> al = new ArrayList<Integer>();
		
		for(int i = 0; i < sizeOfMatrix; i++) {
			for(int j = 0; j < sizeOfMatrix; j++) {
				// 덩어리 묶음의 처음 발견된 index
				 if(matrix[i][j] == 1 && !check[i][j]) {
					  count++;
					 	check[i][j] = true;
					  al.add(bfs(sizeOfMatrix, matrix, i , j));
				 }
			}
		}	
		Collections.sort(al);
																			
		System.out.println(count);
		for(int value : al)
				System.out.print(value + " ");
  }
	
	//덩어리의 첫번쨰 index를 통해 주변에 몇개의 덩어리가 있는지 파악 후 return
	private static int bfs(int size, int[][] array, int i, int j) {        
     	Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {i,j});
				
		int sum = 1;
        while(!queue.isEmpty()){
        	int location[] = queue.poll();

         	for(int direction = 0; direction < 4; direction++){
            	int r = location[0] + x[direction];
            	int c = location[1] + y[direction];

        	    if(r >= 0 && c >= 0 && r < size && c < size) {
              	  if(array[r][c] == 1 && !check[r][c]) {
                 		check[r][c] = true;
						sum++;
       		            queue.add(new int[] {r,c});
                  }
  	            }
            }
		 }
		 return sum;
	}
}

 

• 맞을 결과