[프로그래머스] Level2 _1829번: 카카오 프렌즈 컬러링북 (JAVA)

[프로그래머스] Level2 _1829번: 카카오 프렌즈 컬러링북 (JAVA)

728x90

문제

https://programmers.co.kr/learn/courses/30/lessons/1829

풀이코드

package seohae.algorithm.level2; import java.util.*; /** * https://programmers.co.kr/learn/courses/30/lessons/1829 */ public class Lesson_051_1829 { static int graph[][]; static boolean[][] visited; static int N; static int M; static int count = 0; public static void main(String[] args) { Lesson_051_1829 lesson = new Lesson_051_1829(); int[][] a = new int[][] { {1,1,1,0}, {1,2,2,0}, {1,0,0,1}, {0,0,0,1}, {0,0,0,3}, {0,0,0,3}}; System.out.println(Arrays.toString(lesson.solution(6, 4, a))); } public int[] solution(int m, int n, int[][] picture) { graph = picture; M = m; N = n; visited = new boolean[M][N]; int numberOfArea = 0; int maxSizeOfOneArea = 0; List list = new ArrayList<>(); for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { count = 0; if (graph[i][j] != 0 && !visited[i][j]) { dfs(i, j); numberOfArea++; /* 영역의 개수 */ list.add(count); /* 리스트에 결과 count 요소 add */ } } } /* max 값 설정 */ maxSizeOfOneArea = list.stream() .mapToInt(x -> x) .max().getAsInt(); int[] answer = new int[2]; answer[0] = numberOfArea; answer[1] = maxSizeOfOneArea; return answer; } static void dfs(int x, int y) { visited[x][y] = true; count++; /* 같은 숫자의 개수 */ int[] dx = new int[]{0, -1, 0, 1}; int[] dy = new int[]{1, 0, -1, 0}; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < M && ny < N) { /* 같은 색은 같은 구역으로 본다, count 가 증가되지 않는다 */ if (graph[x][y] != 0 && graph[x][y] == graph[nx][ny]) { if (!visited[nx][ny]) { dfs(nx, ny); } } } } } }

지금까지 풀어온 기존 DFS, BFS 예제와 동일한 풀이이다. 구하고자 하는 것은 영역의 개수이고, 해당 영역의 최대 개수이다. 그러므로 행렬의 for문 실행시마다 새로운 영역의 시작임으로 numberOfArea++; 코드를 실행해주었고, dfs 함수 내에 dfs 호출 개수 (count++) 를 리스트에 담고 최대 값을 maxSizeOfOneArea 변수에 셋팅했다. 마지막으로 행렬의 요소가 0일 경우에는 호출하지 않는다.

from http://devfunny.tistory.com/496 by ccl(A) rewrite - 2021-09-25 17:27:23