★[200526] 카카오프렌즈 컬러링북 - 2017 카카오코드 예선(level2)
1. 문제이해
- 영역의 개수와 가장 큰 영역의 넓이 구하기
- 영역 : 상하좌우로 연결된 같은 색상의 공간
- 입력 : 그림의 크기 m, n(mxn의 그림), picture(2차원 배열. 각 칸의 색상 표시)
- 출력 : [numberOfArea, maxSizeOfOneArea]
2. 전략
(1) DFS(Depth First Search) _ 상,하,좌,우에서 같은 색이 발견되면 거기서부터 다시 search
- boolean[][] visited : 방문했는지 확인하는 배열. 방문 시에 true로 바꿔준다.
- color : 시작칸의 색상값
- Stack<int[]> stack : 조건에 만족하는 칸을 stack에 넣는다. stack이 empty()일 때까지 아래 과정 반복
(1) target 설정 : stack.pop() / a : target[0], b : target[1]
(2) count 증가 : maxSizeOfOneArea와 비교할 것
(3) 상하좌우 색상값과 비교 && 방문했는지 확인
: visited를 true로 바꿔주고, stack에 넣어준다.
- count값을 return
(2) return할 값들 갱신 : picture가 0이 아니고(색칠된 영역) 방문하지 않았던 영역일 때
- DFS수행 후 maxSizeOfOneArea 갱신
- numberOfArea++
3. 참고사항
(1) DFS와 BFS : 인접행렬 혹은 인접리스트를 통해 구현한다.
- DFS : 깊이 우선 탐색. 재귀 혹은 스택구조를 이용한다.
(**단, 재귀를 사용할 때는 StackOverFlow가 발생할 수 있으니 유의하자!! _ 호출한 함수가 저장되는 스택이 꽉 참)
- BFS : 너비 우선 탐색. 큐를 이용한다.
(2) 배열의 초기화
- int[] array = new int[]{a, b}
(3) 제어자
- static : 전역 변수(클래스 변수), 클래스 메소드를 만들 때 사용
**특징**
- 프로그램 시작시 단 한번만 생성, 초기화
- 인스턴스 생성하지 않고 바로 사용 가능
- 해당 클래스의 모든 인스턴스가 공유 = 전역변수, 메소드
(http://tcpschool.com/java/java_modifier_ectModifier)
(4) 기타 사항
: 왜인지 모르겠으나 visited 배열을 picture 그대로를 복사해 0으로 바꾸는 방식이 테스트 케이스에서는 맞았으나 제출시에는 틀렸다...왜인진 모르겠다...
4. 코드
import java.util.*;
class Solution {
static boolean[][] visited;
public int[] solution(int m, int n, int[][] picture) {
visited = new boolean[m][n];
int count = 0;
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(picture[i][j] != 0 && !visited[i][j]){
count = DFS(i, j, m, n, picture);
maxSizeOfOneArea = Math.max(maxSizeOfOneArea, count);
numberOfArea++;
}
}
}
int[] answer = new int[2];
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
public int DFS(int a, int b, int m, int n, int[][] p){
Stack<int[]> stack = new Stack<>();
int count = 0;
int color = p[a][b];
visited[a][b] = true;
stack.push(new int[]{a,b});
while(!stack.empty()){
int[] target = stack.pop();
a = target[0]; b = target[1];
count++;
if(a > 0){
if(p[a-1][b] == color && !visited[a-1][b]){
visited[a-1][b] = true;
stack.push(new int[]{a-1,b});
}
}
if(a < m-1){
if(p[a+1][b] == color && !visited[a+1][b]){
visited[a+1][b] = true;
stack.push(new int[]{a+1,b});
}
}
if(b > 0){
if(p[a][b-1] == color && !visited[a][b-1]){
visited[a][b-1] = true;
stack.push(new int[]{a,b-1});
}
}
if(b < n-1){
if(p[a][b+1] == color && !visited[a][b+1]){
visited[a][b+1] = true;
stack.push(new int[]{a,b+1});
}
}
}
return count;
}
/*public void DFS(int a, int b, int m, int n){ //(4) 기타사항
int color = p[a][b];
p[a][b] = 0;
count++;
if(a > 0){
if(p[a-1][b] == color) DFS(a-1, b, m, n);
}
if(a < m-1){
if(p[a+1][b] == color) DFS(a+1, b, m, n);
}
if(b > 0){
if(p[a][b-1] == color) DFS(a, b-1, m, n);
}
if(b < n-1){
if(p[a][b+1] == color) DFS(a, b+1, m, n);
}
}*/
}