본문 바로가기
알고리즘/프로그래머스

[프로그래머스] 카카오프렌즈 컬러링북 (재귀)

by 코리늬 2020. 2. 16.

문제링크

 

코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스

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

 

그래프 조건에서 == 1 일 때와, != 0 인 경우의 차이점은 뭘까.

무조건 == 1로만 생각하고 풀었더니 성공하지 못했다.

 

백준2667 단지번호 붙이기

 

[백준] 2667번 단지번호붙이기 Java (DFS, BFS)

그래프 관련 문제들의 유형이 다 비슷비슷 한 것 같아보인다. 확실히 짚고 넘어가야 할 필요를 느꼈다. 물론 돌아서면 까먹어서 문제.. 문제링크 2667번: 단지번호붙이기 <그림 1>과 같이 정사각형 모양의 지도가..

n1tjrgns.tistory.com

위 문제와 상당히 비슷하다고 생각하여 똑같이 풀이를 하였는데, 위 조건 때문에 실패 요인이었다.

월요일에 출근해서 물어봐야지..

 

문제 풀이

//link : https://programmers.co.kr/learn/courses/30/lessons/1829
//ref : https://twpower.github.io/151-bfs-dfs-basic-problem
public class KakaoColoringBook {

    private static int[] dx = {0,0,1,-1};
    private static int[] dy = {1,-1,0,0};

    private static boolean[][] visited = new boolean[100][100];
    private static int[][] map = new int[100][100];

    private static int count = 0;

    private static ArrayList<Integer> list = new ArrayList<>();

    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        map = new int[m][n];
        visited = new boolean[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                //0이 아니고 방문하지 않았다면
                if(picture[i][j] != 0 && !visited[i][j]){
                    count = 0;
                    numberOfArea++; // 방문 구역 ++
                    dfs(i,j,picture,m,n);
                    //한 구역을 탐색이 끝나면 크기 영역 크기 비교
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, count);
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

        return answer;
    }

    private void dfs(int x, int y, int[][] picture, int m, int n) {
        int now = picture[x][y];
        visited[x][y] = true;
        count++;
        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){
                if(picture[nx][ny] == now && !visited[nx][ny]){
                    dfs(nx,ny,picture,m,n);
                }
            }
        }
    }

    public static void main(String[] args) {
        KakaoColoringBook k = new KakaoColoringBook();

        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(k.solution(m,n,picture)));
    }
}

댓글