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

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

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

DFS 를 활용해서 풀었다. (bfs로 접근해도 된다)

프로그래머스 버그인지는 모르겠는데

1. 파라미터로 주어진 2차원 배열 값을 조작하면 테스트케이스 통과 안됨

2. 전역변수 초기화를 바로하면 테스트케이스 통과 안됨

이러한 증상이 있어서 다소 불필요한 코드들이 들어갔다;;

public class 카카오프렌즈_컬러링북 {

    static int[][] dirs;

    public static int[] solution(int m, int n, int[][] picture) {
		// 전역변수를 여기서 초기화(상하좌우 설정 값)
        dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        // 원본 이차원배열 대신 카피한 변수 사용
        int[][] arr = new int[m][n];
        copy(picture, arr, m, n);
        int areaCount = 0;
        int maxCount = 0;

		// 2중 포문으로 탐색
        for(int x = 0; x < arr.length; x++) {
            for(int y = 0; y < arr[0].length; y++) {
                if(arr[x][y] != 0) {
                    areaCount++;
                    maxCount = Math.max(dfs(arr, x, y, m, n, arr[x][y], 0), maxCount);
                }
            }
        }
        return new int[]{ areaCount, maxCount };
    }

    public static int dfs(int[][] picture, int x, int y, int m, int n, int ori, int visited) {
        // 탈출 조건
        if(x < 0 || x >= m || y < 0 || y >= n || picture[x][y] == 0 || picture[x][y] != ori) {
            return 0;
        }

        // 방문했으면 0로 전환
        picture[x][y] = 0;
        visited++;
        
        // 상하좌우 탐색(재귀)
        for(int[] dir : dirs) {
            visited += dfs(picture, x + dir[0], y + dir[1], m, n, ori, 0);
        }
        return visited;
    }

    public static void copy(int[][] picture, int[][] arr, int m, int n) {
        for (int i = 0; i < m; i++) {
            if (n >= 0) System.arraycopy(picture[i], 0, arr[i], 0, n);
        }
    }
}

 

테스트케이스 참고

package programmers.level2.카카오프렌즈_컬러링북;

import org.junit.Assert;
import org.junit.Test;
import programmers.level2.더맵게.더맵게;

public class 카카오프렌즈_컬러링북Test {
    @Test
    public void solution1() {
        // given
        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}};
        int m = 6;
        int n = 4;

        // when
        카카오프렌즈_컬러링북 s = new 카카오프렌즈_컬러링북();
        int[] result = s.solution(m, n, picture);
        
        // then
        Assert.assertArrayEquals(result, new int[]{4, 5});

    }
    @Test
    public void solution2() {
        // given
        int[][] picture = {{0, 1, 0}, {1, 1, 0}, {0, 0, 0}};
        int m = 3;
        int n = 3;

        // when
        카카오프렌즈_컬러링북 s = new 카카오프렌즈_컬러링북();
        int[] result = s.solution(m, n, picture);
        
        // then
        Assert.assertArrayEquals(result, new int[]{1, 3});

    }
    @Test
    public void solution3() {
        // given
        int[][] picture = {{0, 0}};
        int m = 1;
        int n = 2;

        // when
        카카오프렌즈_컬러링북 s = new 카카오프렌즈_컬러링북();
        int[] result = s.solution(m, n, picture);
        
        // then
        Assert.assertArrayEquals(result, new int[]{0, 0});
    }
    @Test
    public void solution4() {
        // given
        int[][] picture = {{1, 0}, {0, 1}};
        int m = 2;
        int n = 2;

        // when
        카카오프렌즈_컬러링북 s = new 카카오프렌즈_컬러링북();
        int[] result = s.solution(m, n, picture);
        
        // then
        Assert.assertArrayEquals(result, new int[]{2, 1});
    }
    @Test
    public void solution5() {
        // given
        int[][] picture = {{1, 0, 2}, {0, 1, 2}};
        int m = 2;
        int n = 3;

        // when
        카카오프렌즈_컬러링북 s = new 카카오프렌즈_컬러링북();
        int[] result = s.solution(m, n, picture);
        
        // then
        Assert.assertArrayEquals(result, new int[]{3, 2});
    }
    @Test
    public void solution6() {
        // given
        int[][] picture = {{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}
                , {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}
                , {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}
                , {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}
                , {0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0}
                , {0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0}
                , {0, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 0}
                , {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0}
                , {0, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 0}
                , {0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 0}
                , {0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 0}
                , {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}
                , {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}};
        int m = 13;
        int n = 16;

        // when
        카카오프렌즈_컬러링북 s = new 카카오프렌즈_컬러링북();
        int[] result = s.solution(m, n, picture);
        
        // then
        Assert.assertArrayEquals(result, new int[]{12, 120});
    }
}