백준 알고리즘[재귀] 12100 - 2048(Easy)

https://www.acmicpc.net/problem/12100

    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main {
        public static int[][] maps;
        public static int n,max, count;
        
        
        public static void main(String[] args) throws FileNotFoundException {
            //FileInputStream fi = new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\Solution\\src\\data.txt");
            Scanner sc = new Scanner(System.in);
            //Scanner sc = new Scanner(fi);
            
            n = sc.nextInt();
            maps = new int[n+1][n+1];
            max =0;
            for(int i=1;i<n+1;i++){
                for(int j=1;j<n+1;j++){
                    maps[i][j]=sc.nextInt();
                    if(maps[i][j]>max)
                        max=maps[i][j]; // 입력받은 수 중 가장 큰 값 저장
                }
            }
            count = 0;
            move(0, maps); // 재귀함수 이용
            System.out.println(max);    
        }
        
    /*    -----------------------------------------------------------------*/
    /*            
     *         1번째 Maps에서 L,R,U,D 를 해준다.
            L의 경우,
            회전 후 row, col 이 1~n번째 인덱스가 있음을 가정하고,
            순회1) col 1~n까지 순회하는 동안 내부에서는
            순회 2)row i = 1~n-1 까지 순회하고 
            순회 3(그 안에서 j=i+1~n 까지 순회하여 0이 아닌 같은 숫자가 있으면 더해주고(L방향으로 하나는 sum 다른 하나는 0으로 교환),
            다른 숫자라면 더할 수 없으므로 다음 row로 넘어가 같은 수 탐색한다.
            각 라인에 합한 수가 구해졌다면, pullNumber()함수를 통해 숫자 중간에 0의 공백이 있으면 당겨준다.
            1번째 L에서 또 move호출, 2번째 L,R,U,D 진행하여 5번째에 break; 해준다.
    */
            
        
    /*    -----------------------------------------------------------------*/
        
        public static void move(int _count, int[][] _maps){ // 입력받은 맵을 LRUD 다 해줌
                int count = _count;
            
                if(count<5){
                int[][] copiedMaps = new int[n+1][n+1];
                for(int a=1;a<5;a++){ // LRUD 해주기
                    if(a==1){
                            copiedMaps = copyMaps(_maps); // 배열 복사(값이 아닌 주소를 받아오기 때문에 대입은 금지.)
                            for(int lCol=1;lCol<n+1;lCol++){ // 각 Col 마다 숫자를 더하고 정렬한다.
                                for(int lRow=1;lRow<n;lRow++){ // pivot을 이용해 같은 숫자가 있으면 더해준다. 0 0 1 1 경우, 0 0 2 0 으로 변함.
                                    if(copiedMaps[lCol][lRow]!=0){ // 0이 아닌 수를 비교해야 함.
                                        for(int point = lRow+1; point<=n;point++){ // row+1 ~ n 까지 같은 수 탐색
                                            if(copiedMaps[lCol][point]!=0){  // 0이 아닌 경우, 같은지 다른지 비교 후 같다면 합해준다.
                                                if(copiedMaps[lCol][lRow]==copiedMaps[lCol][point])
                                                    copiedMaps = sumNumber(copiedMaps,1,lCol,lRow,point);
                                                break; // 숫자의 동등 여부 비교했으므로 다음 row를 탐색.
                                            }
                                        }
                                    }
                                    
                                }
                                copiedMaps = pullNumber(copiedMaps, 1, lCol, 0); // 0 0 2 0 을 2 0 0 0 으로 당겨주는 역할.
                            }
                            move(count+1,copiedMaps);
                    }
                    if(a==2){
                            copiedMaps = copyMaps(_maps);
                            for(int lCol=1;lCol<n+1;lCol++){ 
                                for(int lRow=n;lRow>1;lRow--){ 
                                    if(copiedMaps[lCol][lRow]!=0){
                                        for(int point = lRow-1; point>=1;point--){
                                            if(copiedMaps[lCol][point]!=0){ 
                                                if(copiedMaps[lCol][lRow]==copiedMaps[lCol][point])
                                                    copiedMaps = sumNumber(copiedMaps,2,lCol,lRow,point);
                                                break;
                                            }
                                        }
                                    }
                                    
                                }
                                copiedMaps = pullNumber(copiedMaps, 2, lCol, 0);
                            }
                            move(count+1,copiedMaps);
                    }
                    if(a==3){
                            copiedMaps = copyMaps(_maps);
                            for(int lRow=1;lRow<n+1;lRow++){
                                for(int lCol=1;lCol<n;lCol++){
                                    if(copiedMaps[lCol][lRow]!=0){
                                        for(int point = lCol+1; point<=n;point++){
                                            if(copiedMaps[point][lRow]!=0){
                                                if(copiedMaps[lCol][lRow]==copiedMaps[point][lRow])
                                                    copiedMaps =sumNumber(copiedMaps,3,lCol,lRow,point);
                                                break; 
                                            }
                                        }
                                    }
                                    
                                }
                                copiedMaps =pullNumber(copiedMaps, 3, 0, lRow);
                            }
                            move(count+1,copiedMaps);
                    }
                    if(a==4){
                            copiedMaps = copyMaps(_maps);
                            for(int lRow=1;lRow<n+1;lRow++){ 
                                for(int lCol=n;lCol>1;lCol--){
                                    if(copiedMaps[lCol][lRow]!=0){
                                        for(int point = lCol-1; point>=1;point--){
                                            if(copiedMaps[point][lRow]!=0){ 
                                                if(copiedMaps[lCol][lRow]==copiedMaps[point][lRow])
                                                    copiedMaps =sumNumber(copiedMaps,4,lCol,lRow,point);
                                                break;
                                            }
                                        }
                                    }
                                    
                                }
                                copiedMaps = pullNumber(copiedMaps, 4, 0, lRow);
                            }
                            move(count+1,copiedMaps);
                    }
                        
                                
                }
                }
        }
    
        public static int[][] sumNumber(int[][] copiedMaps, int dir, int lCol, int lRow, int point) {
            if(dir==2 || dir ==1) //L,R 인 경우 좌 우로 더함{
            {    
                copiedMaps[lCol][lRow]+=copiedMaps[lCol][point];
                copiedMaps[lCol][point]=0;
            }
            else // U,D 인 경우 위 아래로 더함
            {    
                copiedMaps[lCol][lRow]+=copiedMaps[point][lRow];
                copiedMaps[point][lRow]=0;
            }
            if(copiedMaps[lCol][lRow]>max)
                max = copiedMaps[lCol][lRow];
            
            return copiedMaps;
            
        }
    
        public static int[][] copyMaps(int[][] _maps) {
            int maps[][] = new int[n+1][n+1];
            for(int i=1;i<n+1;i++){
                for(int j=1;j<n+1;j++){
                    maps[i][j]=_maps[i][j];
                }
            }
            return maps;
        }
        
        public static int[][] pullNumber(int[][] copiedMaps, int dir, int Col, int Row){
            
            
            switch(dir){
            case 1:{ // Left 0 당긴다.
                    for(int point=1;point<n;point++){ // point와 idx를 이용해  point 이후에 0이 있으면 앞으로 당겨준다.
                        if(copiedMaps[Col][point]==0){
                            for(int idx=point+1;idx<=n;idx++){
                                if(copiedMaps[Col][idx]!=0){
                                    copiedMaps[Col][point]=copiedMaps[Col][idx];
                                    copiedMaps[Col][idx]=0;
                                    break;
                                }
                            }
                        }
                    }
                    break;
                
            }
            case 2:{ // R 0 당김
                for(int point=n;point>1;point--){ // point와 idx를 이용해  point 이후에 0이 있으면 뒤로 당겨준다.
                    if(copiedMaps[Col][point]==0){
                        for(int idx=point-1;idx>=1;idx--){
                            if(copiedMaps[Col][idx]!=0){
                                copiedMaps[Col][point]=copiedMaps[Col][idx];
                                copiedMaps[Col][idx]=0;
                                break;
                            }
                        }
                    }
                }
                break;
            }
            case 3:{ // UP 0 당김
                for(int point=1;point<n;point++){ // point와 idx를 이용해  point 이후에 0이 있으면 앞으로 당겨준다.
                    if(copiedMaps[point][Row]==0){
                        for(int idx=point+1;idx<=n;idx++){
                            if(copiedMaps[idx][Row]!=0){
                                copiedMaps[point][Row]=copiedMaps[idx][Row];
                                copiedMaps[idx][Row]=0;
                                break;
                            }
                        }
                    }
                }
                break;
            }
            
            case 4:{ // D 0 당기기
                for(int point=n;point>1;point--){ // point와 idx를 이용해  point 이후에 0이 있으면 뒤로 당겨준다.
                    if(copiedMaps[point][Row]==0){
                        for(int idx=point-1;idx>=1;idx--){
                            if(copiedMaps[idx][Row]!=0){
                                copiedMaps[point][Row]=copiedMaps[idx][Row];
                                copiedMaps[idx][Row]=0;
                                break;
                            }
                        }
                    }
                }
                    
            }
            break;
            }
            
            return copiedMaps;
        }
        
    }

풀이시간 ) 3시간 반;;;;

풀이 )

각 방향(L,R,U,D) 기준 각 라인의 수를 비교해 SUM을 구하고 PULL하여 빈 공백(0)이 있으면 당겨주었다.

예를 들어

nxn의 배열이 있다고 가정하고(1~N까지)

특정 COL이 다음과 같이 주어진 경우, L할 경우

 

1 0 0 1 0 0 2 4 4  

2 0 0 0 0 0 2 4 4 

(ROW R=1~n-1까지 탐색, 그 내부에서 POINT=ROW+1~n 까지 탐색해서  POINT가 0이 아닌 수이면서, POINT=r이면 더해주고 아니면 다음 ROW로 BREAK) 

2 0 0 0 0 0 2 4 4

2 0 0 0 0 0 2 8 0

2 2 8 0 0 0 0 0 0 

Left부터 빈공백(0)이 있으면 당겨준다.

다른 풀이)

for(각각의 라인){

빈 공백을 당겨준 후 => 인접 인덱스가 같으면 SUM 해주고 => 다시 빈 공백을 당겨준다.

}

주의할 점

SWITCH CASE 종료시 꼭 BREAK 해줄 것. 아니면 다음 CASE가 실행된다.