[JAVA] 백준 - 14620 꽃길 (feat. JAVA 얕은 복사, 깊은 복사)

🕶️ 문제 풀기 앞서 알고 넘어가면 좋은 것

 

모든 경우의 수를 알아야하는 완전 탐색 문제이다.

본인은 완전탐색 같은 문제를 풀 때, 문제마다 다르지만

보통 재귀함수를 사용하는 편이다. 

A라는 경우에서 -> B 경우를 고려하고 -> C 경우 일 때의 최소 or 최대

같은 경우에 해당되는데 앞선 단계에서 ~~는 이미 고려했다! 라는 정보를

메모라이징 하기 위해 boolean형식의 visit를 사용해 true, false 처리를 해주고,

재귀를 하는 메서드의 파라미터로 넘겨주곤 하는데

이번 문제에서는 재귀 호출하는 B(=A)라는 메서드에서 return 후 상위 스택의 동일한 메서드

A로 갔을 때 visit의 상태가 바뀌지 않아서 의도한 결과 값이 나오지 않아 애를 먹었다.

명확하게는 visit의 상태가 재귀 이전으로 돌아가지 않았음.

 

위 현상은 재귀 이전 visit와 재귀 이후 visit의 주소값이 같아서 생기는

얕은 복사 때문이었다. 따라서 다른 주소값을 갖게 하기 위해(깊은 복사)

재귀 호출 이전에 visit 배열을 clone 하고 파라미터로 넘겨주었지만 visit의 상태는 바뀌지 않았다.

 

검색해보니 1차원 배열 같은 경우 clone을 통해 깊은 복사가 가능하지만

내가 이번 문제에서 사용한 visit가 2차원 배열이었고 2차원 배열은

clone메서드를 사용하면 객체들을 담고 있는 주소의 주솟값데이터를 새로 생성해 복사하기 때문에

얕은 복사가 된 것이다. 따라서 2차원 for loop를 통해 visit 배열의 상태를 일일히 바꿔주었다.

 

<참고>

https://hanyeop.tistory.com/366

[Java] 자바 1차원, 2차원 배열 복사 (얕은 복사, 깊은 복사)

 

 

✅ 핵심 풀이

꽃잎끼리 닿거나 꽃잎이 map 밖으로 나가면 안되므로

map 탐색의 시작을 (1,1) - 끝을 (n,n) 이라고 했을 때 1,1부터 시작해서 맵을 나가는 경우에 대한

예외처리를 해줄까 했지만, 아예 탐색 시작을 (2,2) - 끝을 (n-1,n-1) 로 해주면

map 밖에 나가는 경우에 대한 예외처리를 생략과 실행시간 단축을 할 수 있다. 

또한 위에 서술했던 얕은복사 깊은복사 이슈를 생각해 재귀 이후 반복문을 통해

visit의 상태를 변경했다.

 

🚨 CODE

import java.io.*;
import java.util.*;

public class Main {

	static int[][] map;
	static boolean[][] visit;
	static int result = Integer.MAX_VALUE;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n;
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		visit = new boolean[n+1][n+1];
		StringTokenizer st;
		for(int i = 1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j<=n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		find(0,0);
		System.out.println(result);
	}
	public static void find(int count, int sum) {
		if(count == 3) {
			result = Math.min(sum, result);
			return;
		}
		
		for(int i = 2; i<n; i++) {
			for(int j = 2; j<n; j++) {
				// i,j 가 2,2 부터 n-1,n-1까지 탐색하므로
				// map을 벗어나는 것에 대한 예외처리는 생략가능하다.
				// 씨를 뿌릴 좌표가 이미 visit인지 확인한다
				if(visit[i][j])
					continue;
				// 상하좌우의 좌표가 이미 visit인지 확인한다
				if(isVisited(i,j))
					continue;
				
				visit[i][j] = true;
				find(count+1, sum+getSum(i,j));
				
				initVisit(i,j);
				visit[i][j] = false;
			}
		}
		
	}
	public static boolean isVisited(int x, int y) {
		for(int i = 0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(visit[nx][ny])
				return true;
		}
		return false;
	}
	public static int getSum(int x, int y) {
		int curSum = map[x][y];
		for(int i = 0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			visit[nx][ny] = true;
			curSum += map[nx][ny];
		}
		return curSum;
	}
	public static void initVisit(int x, int y) {
		for(int i = 0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			visit[nx][ny] = false;
		}
	}
}