기본적인 BFS 문제입니다. 그림에 있는 영역의 개수와 그 중 가장 큰 영역의 칸의 개수를 구하면 됩니다.
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Solution {
static class Dir{
int y, x;
Dir(int y, int x){
this.y = y; this.x = x;
}
}
public static boolean isIn(Dir c, int m, int n) {
if(0<= c.y && c.y < m && 0<= c.x & c.x < n ) return true;
else return false;
}
public static int bfs(Dir s, int[][] picture, boolean[][] v, int m, int n) {
int[] dy = {1, -1, 0, 0};
int[] dx = {0, 0, 1, -1};
int size = 1;
Queue<Dir> q = new LinkedList<Dir>();
q.offer(s);
v[s.y][s.x] = true;
while(!q.isEmpty()) {
Dir cur = q.poll();
for(int i = 0; i< 4; i++) {
Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
if(!isIn(next, m, n)) continue;
if(v[next.y][next.x]) continue;
if(picture[cur.y][cur.x] != picture[next.y][next.x]) continue;
v[next.y][next.x] = true;
q.offer(next);
size++;
}
}
return size;
}
public static int[] solution(int m, int n, int[][] picture) {
List<Integer> sizeList = new LinkedList<Integer>();
int[] answer = new int[2];
boolean [][] visited = new boolean[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(picture[i][j] == 0 || visited[i][j]) continue;
sizeList.add(bfs(new Dir(i, j), picture, visited, m, n));
}
}
answer[0] = sizeList.size();
answer[1] = Collections.max(sizeList);
return answer;
}
}
프로그래머스는 solution 메소드에 파라미터로 입력이 들어와서 다른 메소드들 파라미터가 좀 지저분합니다..
picture 배열을 탐색하면서 원소값이 0이 아니거나 한 번도 방문한 적이 없다면 BFS를 돌려서 인접한 네 방향에 있는 친구중 같은 색깔(숫자)인 친구들을 체크해줍니다. 이 때 가장 큰 영역의 크기도 구해주어야 하기 때문에 BFS를 돌리는 메소드에서 거기서 구한 영역의 크기를 리턴해서 저장해 둡니다.
pucture 배열을 다 탐색하면 sizeList에는 영역의 개수만큼 각 영역의 크기가 들어 있습니다.
따라서 리턴할 answer 배열에 sizeList의 크기와 sizeList의 원소중 최댓값을 넣어서 리턴해주면 끝입니다.
Collections의 max를 사용하면 바로 최댓값을 구할 수 있답니다.
감사합니다.
'Algorithm > Programmers' 카테고리의 다른 글
[2020 KAKAO BLIND RECRUITMENT][시뮬레이션/완전 탐색] 자물쇠와 열쇠 - Java (0) | 2020.08.25 |
---|---|
[2020 KAKAO BLIND RECRUITMENT][문자열 처리] 괄호 변환 - Java (0) | 2020.08.24 |
[2020 KAKAO BLIND RECRUITMENT][문자열 처리] 문자열 압축 - Java (0) | 2020.08.24 |
[2018 KAKAO BLIND RECRUITMENT][문자열 처리] [1차] 비밀지도 - Java (0) | 2020.08.15 |
[Summer/Winter Coding(2019)][시뮬레이션] 종이접기 - Java (0) | 2020.06.23 |