칸비

개발 찍어먹기

[Programmers]-카카오프렌즈 컬러링북

문제

문제

이번 프로그래머스 문제는 카카오프렌즈 컬러링북 입니다.

문제 풀이

dfs와 bfs 알고리즘으로 쉽게풉니다.

이 알고리즘이 많이 지워진 상태여서 공부 후 포스팅해볼 예정이다.

공부는 했지만 정리가 안됐다.

**문제풀이 **

  • dfs를 이용한 재귀함수

주석에 상세하게 적어 놓았다. 코드가 길지만 어렵지 않다.

class Solution {
    int count;
    
    boolean[][] visited;
    
    int[] dirX = {1, 0, -1, 0};//우,하,좌,상
    int[] dirY = {0, 1, 0, -1};
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;//나눠진 영역 수
        int maxSizeOfOneArea = 0;//영역중 가장 큰 범위

        int[][] draw = new int[m+2][n+2];//복제할 배열
        visited = new boolean[m+2][n+2];//방문 여부 배열
        
        for(int i=0;i<m;i++){//clone
            for(int j=0;j<n;j++){
                draw[i+1][j+1] = picture[i][j];
            }
        }

        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                if(draw[i][j]!=0&&!visited[i][j]){//색칠되어있고 방문하지 않았을 경우
                    count = 1;//draw[i][j]를 포함해야해서 1초기화
                    dfs(i, j, draw);
                    //재귀를 다 마치면 재귀한 만큼 count가 쌓임
                    if(maxSizeOfOneArea<count) maxSizeOfOneArea = count;//최대치
                    
                    numberOfArea++;//한 영역(사이클) 돌면서 영역 추가
                }
            }
        }       
        int[] answer = new int[2];    
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    public void dfs(int x, int y, int[][] draw){
        visited[x][y] = true;//방문했음
        
        for(int i=0;i<4;i++){
            int xx = x + dirX[i];//비교 x
            int yy = y + dirY[i];//비교 y
            
            if(draw[x][y]==draw[xx][yy] && !visited[xx][yy]){//같거나 방문안했을경우 재귀
                count++;
                dfs(xx,yy,draw);
            }
        }
    }
}

dfs/bfs알고리즘은 졸업작품을 끝마치고 포스팅해볼 예정이다.

dfs로 풀어보았으니 bfs로도 풀어서 포스팅할 예정

참고