Menu

Subscribe

[JAVA/프로그래머스] 2017 카카오코드 예선: 카카오프렌즈 컬러링북

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. DFS로 배열을 순회하며 영역 개수를 센다.
  2. picture 크기와 같은 int형 visit 배열을 생성하고, 위치를 방문했을 때 picture값을 넣어 중복 탐색을 방지한다.
  3. 영역별로 체크가 끝날 때 마다 max에 영역 개수의 최대값을 저장한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    int[][] visit; // 방문 체크 배열
    ArrayList<Integer> list; // 영역별 넓이 저장
    int cnt, max; // 탐색하고 있는 영역의 넓이, 전체 영역 넓이 중 최대값
    int[] dotX={0,1,0,-1};
    int[] dotY={1,0,-1,0};
    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        
        visit=new int[m][n];
        list=new ArrayList<>();
        max=0;
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                // 색깔이 있고 방문하지 않는 곳이면 해당 영역 찾기
                if(picture[i][j]!=0 && visit[i][j]==0){
                    cnt=1;
                    dfs(i, j, m, n, picture);
                    // 영역 탐색 완료 후 max, list에 값 저장
                    max=Math.max(max, cnt);
                    list.add(cnt);
                }
            }
        }        
        
        answer[0] = list.size();
        answer[1] = max;
        return answer;
    }
    
    public void dfs(int x, int y, int m, int n, int[][] picture){
        visit[x][y]=picture[x][y]; // 방문했음을 표시
        
        for(int i=0;i<4;i++){ // 사방으로 갈 수 있는 좌표 계산
            int xx=x+dotX[i];
            int yy=y+dotY[i];
            if(xx<0 || xx>=m || yy<0 || yy>=n) continue; // 범위 초과
            if(visit[xx][yy]!=0) continue; // 방문한 곳이면 패스
            if(picture[xx][yy]==picture[x][y]){ // 현재 탐색 영역과 색깔이 같다면
                cnt++;
                dfs(xx, yy, m, n, picture); // 이동
            }
        }
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. DFS를 이용한다
    • 배열의 영역을 구하는 문제는 주로 DFS를 이용한다.
    • picture 값 별로 같은 영역을 구해야 하므로 visit 배열을 int형으로 선언하여, 방문한 곳이면 picture 값(색깔)을 저장한다.
    • dotX, dotY 배열을 통해 상하좌우로 이동할 수 있는 좌표를 저장한다.
    • for문으로 상하좌우 좌표를 계산하고, 배열 범위와 방문한 곳인지를 체크한다.
    • 탐색하는 영역의 색깔과 같다면(picture[i][j]), 영역이 늘어났으므로 cnt++하고 재귀 호출을 통해 그 곳으로 이동한다.
  2. main에서 picture을 순회하며 색깔이 있고 방문하지 않은 영역을 찾아 dfs를 호출한다
    • 이중 for문을 통해 picture의 모든 원소를 탐색하지만, visit로 방문 여부를 체크하였기 때문에 같은 곳을 두 번 이상 dfs를 사용하는 경우는 없다.

👏 해결 완료!