글 읽기 - 재귀과정에서 배열이 복원되지 않습니다.

whj6973 5년 전 0

그냥 up(arr) right(arr) 식으로 호출을하면 결과는 맞게 나오는데 재귀과정에서 돌아오면서 배열이 복원되지 않습니다.

예를들어 '업->업->업->업->다운' 으로 이동을 마치고 네번째 '업'으로 돌아와서 '업->업->업->업->레프트'이 되야하는데 네번째 '업'의 결과가 아닌 이전 이동에서 '다운'의 결과에서 '레프트'가 됩니다.....

도와주세요 ㅠㅠ

import java.util.Scanner;

public class Main {
    static int n;
    static int[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int max = 0;
    
    static void maxNum(int[][] temp) {
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<n; j++) {
    			max = (temp[i][j]>max) ? temp[i][j] : max;
    		}
    	}
    }
    
    static void dfs(int count, int[][] mat) {
    	int[][] temp = mat;
        /* 배열 복사를 아래 코드로해도 결과는 같습니다.
        int[][] temp = new int[n][n];
    	for(int i=0; i<n; i++){
    		for(int j=0; j<n; j++) {
    			temp[i][j] = mat[i][j];
    		}
    	}*/
    	if(count == 5) {
    		maxNum(temp); 
    		count--;
    		return;
    	} else if(count < 5) {
        	for(int i=0; i<4; i++) {
       			switch(i) {
       				case 0: 
       					dfs(count+1, up(temp));
    					break;
    				case 1: 
    					dfs(count+1, down(temp));
    					break;
    				case 2: 
    					dfs(count+1, left(temp));
    					break;
    				case 3: 
    					dfs(count+1, right(temp));
    					break;
    			}
        	}
    	}
    }
    
    static int[][] up(int[][] temp) {
    	int[][] nArr = temp;
    	for(int j=0; j<n; j++) {
    		for(int i=0; i<n-1; i++) {    // 0이면 위쪽으로 옮겨라
    			int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(i+k >= n) break;
    				nArr[i][j] = nArr[i+k][j];
    				nArr[i+k][j] = 0;
    			}
    		}
    		for(int i=0; i<n-1; i++) {    // 같으면 더해라
    			if(nArr[i][j] == nArr[i+1][j]) {
    				nArr[i][j] += nArr[i+1][j];
    				nArr[i+1][j] = 0;
    			}
    		}
    		for(int i=0; i<n-1; i++) {    // 0이면 위쪽으로 옮겨라
    			int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(i+k >= n) break;
    				nArr[i][j] = nArr[i+k][j];
    				nArr[i+k][j] = 0;
    			}
    		}
    	}
    	return nArr;
    }
    
    static int[][] down(int[][] temp) {
    	int[][] nArr = temp;
    	for(int j=0; j<n; j++) {
    		for(int i=n-1; i>0; i--) {    // 0이면 아래쪽으로 옮겨라
    			int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(i-k < 0) break;
    				nArr[i][j] = nArr[i-k][j];
    				nArr[i-k][j] = 0;
    			}
    		}
    		for(int i=n-1; i>0; i--) {    // 같으면 더해라
    			if(nArr[i][j] == nArr[i-1][j]) {
    				nArr[i][j] += nArr[i-1][j];
    				nArr[i-1][j] = 0;
    			}
    		}
    		for(int i=n-1; i>0; i--) {    // 0이면 아래쪽으로 옮겨라
    			int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(i-k < 0) break;
    				nArr[i][j] = nArr[i-k][j];
    				nArr[i-k][j] = 0;
    			}
    		}
    	}
    	return nArr;
    }
    
    static int[][] left(int[][] temp) {
    	int[][] nArr = temp;
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<n-1; j++) {    // 0이면 왼쪽으로 옮겨라
    			int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(j+k >= n) break;
    				nArr[i][j] = nArr[i][j+k];
    				nArr[i][j+k] = 0;
    			}
    		}
    		for(int j=0; j<n-1; j++) {    // 같으면 더해라
    			if(nArr[i][j] == nArr[i][j+1]) {
    				nArr[i][j] += nArr[i][j+1];
    				nArr[i][j+1] = 0;
    			}
    		}
    		for(int j=0; j<n-1; j++) {    // 0이면 왼쪽으로 옮겨라
    			int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(j+k >= n) break;
    				nArr[i][j] = nArr[i][j+k];
    				nArr[i][j+k] = 0;
    			}
    		}
    	}
    	return nArr;
    }
    
    static int[][] right(int[][] temp) {
    	int[][] nArr = temp;
        for(int i=0; i<n; i++) {
        	for(int j=n-1; j>0; j--) {    // 0이면 오른쪽으로 옮겨라
            	int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(j-k < 0) break;;
    				nArr[i][j] = nArr[i][j-k];
    				nArr[i][j-k] = 0;
                }
            }
            for(int j=n-1; j>0; j--) {    // 같으면 더해라
                if(nArr[i][j] == nArr[i][j-1]) {
                	nArr[i][j] += nArr[i][j-1];
                	nArr[i][j-1] = 0;
                }
            }
            for(int j=n-1; j>0; j--) {    // 0이면 오른쪽으로 옮겨라
            	int k = 0;
    			while(nArr[i][j] == 0) {
    				k++;
    				if(j-k < 0) break;;
    				nArr[i][j] = nArr[i][j-k];
    				nArr[i][j-k] = 0;
                }
            }
        }
        return nArr;
    }
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][n];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        
        dfs(0, arr);
        
        System.out.println(max);
        
    }
}

rdd6584 5년 전 1

질문 내용만 보고 답변하는거라, 원하는 답변이 될지 모르겠네요.

배열을 함수인자로 넘길때 값이 아닌 레퍼런스로 넘겨지기 때문에 말씀하신 증상이 나타나는게 아닐까 싶습니다.

저 같은 경우에는 원본 배열을 따로 빼두고 재귀를 마친다음에 원본 배열을 또 가져오는 방법으로 해결합니다.

memcpy(temp, mat, sizeof(mat));
for (i = x + 1; mat[i][y] == '.'; i++)
mat[i][y] = '*';
c1 = go(i - 1, y) + 1;
memcpy(mat, temp, sizeof(mat));

이런식으로요

whj6973 5년 전 0

배열을 복사할 때 int[][] temp = arr; 식이 아니라

int[][] temp = new int[n][n];

for(int i =0; i<n; i++) {

for(int j=0; j<n; j++) {

temp[i][j] = arr[i][j];

}

식으로 했더니 결과가 맞았습니다ㅎㅎㅎㅎ

dfs()뿐만아니라 up(), down(), left(), right() 모두 위와같이 변경해줘야합니다.

frigrammer 5년 전 0

int arr[][] 대신에 vector<vector<int>> 로 넘기면 call by value로 들어갑니다.

메모리가 넉넉한 문제에서 사용하시면 유용합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

재귀과정에서 배열이 복원되지 않습니다.

whj6973 5년 전 0

rdd6584 5년 전 1

whj6973 5년 전 0

frigrammer 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말