풀이 방법
dfs를 이용해서 연결되어 있는 영역의 갯수를 세어주었다.
way배열로 상하좌우 방향을 이동하도록 하고 check로 체크한 부분인지 확인해주었다.
그림 배열의 처음부터 돌면서 check 되지 않은 부분을 dfs 돌려서 영역 크기를 구하고 최댓값을 구해주었다.
내 코드
class Solution {
static int[][] way = {{1,0}, {-1,0}, {0,1}, {0,-1}};
static boolean[][] check;
public int[] solution(int m, int n, int[][] picture) {
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
check = new boolean[m][n];
for(int i = 0; i< m ;i++){
for(int j = 0; j< n; j++){
if(!check[i][j] && picture[i][j]!=0){
numberOfArea++;
maxSizeOfOneArea = Math.max(dfs(i, j, picture[i][j], picture), maxSizeOfOneArea);
}
}
}
int[] answer = new int[2];
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
static int dfs(int x, int y, int color, int[][] picture){
int num = 0;
if (check[x][y]){
return num;
}
num = 1;
check[x][y] = true;
for(int i = 0; i< 4; i++){
if(x + way[i][0] >= 0 && y + way[i][1] >= 0 && x + way[i][0] < picture.length && y + way[i][1] < picture[0].length && picture[x + way[i][0]][y + way[i][1]] == color)
num += dfs(x + way[i][0], y + way[i][1], color, picture);
}
return num;
}
}
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
뉴스 클러스터링 (0) | 2021.10.08 |
---|---|
단체 사진 찍기 (0) | 2021.10.08 |
전력망을 둘로 나누기 (0) | 2021.10.07 |
최소직사각형 (0) | 2021.10.06 |
입실 퇴실 (0) | 2021.09.17 |