https://programmers.co.kr/learn/courses/30/lessons1829?language=java
class Solution {
public int[] solution(int m, int n, int[][] picture) {
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
boolean[][] visited = new boolean[m][n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(visited[i][j] == false && picture[i][j] != 0){
numberOfArea++;
visited[i][j] = true;
maxSizeOfOneArea = Math.max(dfs(i, j, m, n, 1, picture, visited), maxSizeOfOneArea);
}
}
}
int[] answer = new int[2];
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
int dfs(int x, int y, int m, int n, int cnt, int[][] picture, boolean[][] visited){
int[] dx = new int[] {1,-1,0,0};
int[] dy = new int[] {0,0,1,-1};
for(int d=0; d<4; d++){
int nx = x + dx[d];
int ny = y + dy[d];
if(nx < 0 || nx >= m || ny<0 || ny>= n || picture[nx][ny] != picture[x][y] || visited[nx][ny] == true){
continue;
}
visited[nx][ny] = true;
cnt = dfs(nx, ny, m, n, ++cnt, picture, visited);
}
return cnt;
}
}
picture 값이 0이 아니고 방문한적이 없을 때 dfs()를 호출하여
플러드 필 방식으로 탐색하였습니다.
각 영역의 최대 갯수는
dfs(4)
dfs(3)
dfs(2)
for(4방향 반복){
cnt = dfs(1)
cnt = dfs(5)
cnt = dfs(6)
cnt = dfs(7)
}
이런 방식으로 리턴하여 계산했습니다.
'알고리즘' 카테고리의 다른 글
[프로그래머스] 괄호 변환 - java (0) | 2021.09.23 |
---|---|
[프로그래머스] 단체사진 찍기 - java (0) | 2021.09.23 |
[프로그래머스] 문자열 압축 - java (0) | 2021.09.22 |
[카카오 블라인드 2018] [1차] 캐시 - java (0) | 2021.09.16 |
달팽이 문제 (0) | 2021.09.15 |