문제

Idea

각 배열의 원소를 순회하며 전 원소의 값이 다음원소의 값과 같다면 하나의 영역으로 생각하며 영역의 넓이를 증가하는 전형적인 DFS방식의 문제라고 생각했습니다.

Test case(추가)

13
16
[[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]]

result : [12, 120]

Code(잘못된 소스)

public int[] solution(int m, int n, int[][] picture) {
	       max = 0;
	        int num = 0;//면적의 개수
	        int [][] arr = new int[picture.length][picture[0].length];

	        for(int i = 0; i<arr.length; i++){
	            for(int j = 0; j<arr[i].length; j++){
	                arr[i][j] = picture[i][j];

	            }
	        }

	        for(int i = 0; i<arr.length; i++){
	            for(int j = 0; j<arr[i].length; j++){
	                int target = arr[i][j];
	                if(target != 0){

	                    
	                    

	                    num++;
	                    Test.dfs(i, j, arr, target,1);    
	                   
	                }

	            }
	        }
	        return new int []{num,max};
	    }

	    public static void dfs(int x, int y, int[][]picture, int target, int roof){//행, 열, picturem, 해당 수, 영역의 넓이(dfs method의 호출 depts)


	        if(x < 0 || x >= picture.length || y < 0 || y >= picture[0].length || picture[x][y] != target){//배열의 길이에서 벗어난다면 method 종료
	            max = Math.max(roof, max);
	            return;
	        }
	        roof++;
	        
	            picture[x][y] = 0; // 왔던길 마킹
	            
	            dfs(x+1, y, picture, target, roof); //아래
	            dfs(x-1, y, picture, target, roof); // 위
	            dfs(x, y+1, picture, target, roof); // 우측
	            dfs(x, y-1, picture, target, roof); // 좌측
	    }

Error(요인)

dfs method 내에서 각 영역의 넓이를 카운팅하는 roof 값이 결과값과 일치하지 않는경우가 있었습니다.

Error(이유)

	dfs(x+1, y, picture, target, 1); //아래 A
        dfs(x-1, y, picture, target, 1); // 위 B
        dfs(x, y+1, picture, target, 1); // 우측 C
        dfs(x, y-1, picture, target, 1); // 좌측 D
        
        를 실행할때 paramter로 대입되는 roof의 값이 가령 1이라면 가장먼저 아래의 원소를 체크하는 A가 실행될 때 roof가 증가하지만  B, C, D 의 roof값은 1로 증가하지 않게 됩니다.
        

solution

각 영역의 넓이를 측정하는 roof의 형태가 value가 아닌 Object타입을 참조하게 하면 되겠다는 생각을 했습니다.

영역의 넓이를 나타낼수 있는 객체를 참조하고있다면 아래의 원소를 체크하는 A가 실행될 때 B C D가 참조하고있는 Roof객체안의 value값도 함께 증가하게 되는것입니다.

add class

 public class Roof{
	        private int val;//영역 개수

	        public void setVal(int val){
	            this.val = val;
	        }

	        public int getVal(){
	            return this.val;
	        }


	    }

최종 코드

import java.util.Arrays;

public class Chal008 {//프로그래머스 //2017 카카오코드 예선// 카카오프렌즈 컬러링북

static int max = 0;

public static void main(String[] args) {

	int m = 5;
	int n = 5;
	int [][]picture = {{1, 1, 1, 1, 1}, {1, 0, 0, 0, 1}, {1, 0, 1, 0, 1}, {1, 0, 0, 0, 1}, {1, 1, 1, 1, 1}};
	
	Chal008 app = new Chal008();
	int []result = app.solution(m, n, picture);
	System.out.println("result : "+Arrays.toString(result));

	
}
    public int[] solution(int m, int n, int[][] picture) {
       max = 0;
        int num = 0;//면적의 개수
        int [][] arr = new int[picture.length][picture[0].length];

        for(int i = 0; i<arr.length; i++){
            for(int j = 0; j<arr[i].length; j++){
                arr[i][j] = picture[i][j];

            }
        }

        for(int i = 0; i<arr.length; i++){
            for(int j = 0; j<arr[i].length; j++){
                int target = arr[i][j];
                if(target != 0){

                    Roof roof = new Roof();
                    roof.setVal(0);

                    num++;
                    Chal008.dfs(i, j, arr, target, roof);    
                   
                }

            }
        }
        return new int []{num,max};
    }

    public static void dfs(int x, int y, int[][]picture, int target, Roof roof){//행, 열, picturem, 해당 수, depth


        if(x < 0 || x >= picture.length || y < 0 || y >= picture[0].length || picture[x][y] != target){
            if(roof.getVal() > max){
                max = roof.getVal();
            }
            return;
        }
        roof.setVal(roof.getVal() + 1);
        
            picture[x][y] = 0; // 왔던길 마킹
            
            dfs(x+1, y, picture, target, roof); //아래
            dfs(x-1, y, picture, target, roof); // 위
            dfs(x, y+1, picture, target, roof); // 우측
            dfs(x, y-1, picture, target, roof); // 좌측
    }


    public class Roof{
        private int val;//영역 개수

        public void setVal(int val){
            this.val = val;
        }

        public int getVal(){
            return this.val;
        }


    }

}