Algorithm/프로그래머스
프로그래머스 :: 카카오 프렌즈 컬러링북
jihyun03
2020. 8. 28. 18:30
https://programmers.co.kr/learn/courses/30/lessons/1829
코딩테스트 연습 - 카카오프렌즈 컬러링북
6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5]
programmers.co.kr
🎈 문제 풀이
- DFS를 활용하면 되는 문제였다.
- 다른 문제와 다르게 했던 점은 다음 인접 정점을 탐색하기 위해서는 계속 "같은 색상의 값"이어야 했기
때문에 dfs 파라미터로 처음 dfs 탐색을 시작할 때 가지고 있던 색상 값을 받아서 현재 탐색 중인 정점과 비교했다.
- 한 번 dfs를 돌 때 마다 numberOfArea를 1씩 추가하고
- dfs 호출을 통해서 반환되어져 오는 "영역의 넓이"를 비교하여 maxSizeOfOneArea를 구했다.
🎈 소스 코드
import java.util.Arrays;
public class 컬러링북 {
static int[][] moves = {{-1,0}, {+1,0}, {0,+1}, {0,-1}};
static boolean[][] visited;
public static void main(String[] args) {
int m = 6;
int n = 4;
int[][] picture = {{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(solution(m,n,picture)));
}
static int[] solution(int m, int n, int[][] picture) {
int[] answer = new int[2];
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
visited = new boolean[m][n];
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(!visited[i][j] && picture[i][j] != 0) {
numberOfArea++;
int sizeOfOneArea = dfs(i,j,picture, picture[i][j]);
if(sizeOfOneArea > maxSizeOfOneArea) {
maxSizeOfOneArea = sizeOfOneArea;
}
}
}
}
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
static int dfs(int m, int n, int[][] picture, int value) { // value = 컬러
// 종료조건
if(m < 0 || m >= picture.length || n < 0 || n >= picture[0].length) return 0;
if(picture[m][n] == 0) return 0;
if(visited[m][n]) return 0;
if(picture[m][n] != value) return 0;
int cnt = 1;
visited[m][n] = true; // 방문
for(int[] move : moves) { // 인접정점 돌기
int nx = m+move[0];
int ny = n+move[1];
cnt += dfs(nx, ny, picture, value);
}
return cnt;
}
}