Java의 객체 참조 방식과 call by value + reference semantics

기본적으로 Java는 무조건 call by value이다

객체든 원시타입이든 전부 `값`으로 전달된다.

하지만, 객체일 경우에는 `참조값(reference)`이 값으로 전달된다.

---

기본 타입

void change(int x) {
    x = 100;
}

int a = 10;
change(a);
System.out.println(a); // 결과는 10이 나온다. 100으로 변하지 않는다.

 

보통은 완전한 값 복사의 형태를 띄기 때문에, a 의 값은 바뀌지 않는다.

 

그러나..

참조 타입(객체)

class Box { int value = 10; }

void change(Box b) {
    b.value = 100;
}

Box box = new Box();
change(box);
System.out.println(box.value); // 100 이 출력된다! 값이 바뀐것이다.

 

파라미터 Box b 는 Box box 객체를 가리키는 참조값을 복사한다.

따라서 b.value 의 값을 바꾸면, box.value 의 값도 바뀌는 것이다.

---

이에 따른 DFS 에서 주의할 점.

Fish[][] copiedTank = originalTank; // 얕은 복사

 

위 이중 배열에는 Fish 객체가 정의되어 있다.

기존 originalTank 이중 배열을 복사하려는 로직이지만, 이렇게되면 의미가 없어진다.

 

왜냐하면 복사한 배열인 copiedTank 는 originalTank 의 참조값을 가져올 것이기 때문에,

copiedTank 내부의 Fish 객체를 수정하면 자동으로 originalTank 내부의 Fish 객체도 수정되어버린다.

 

이때 DFS는, 분기별로 다른 상태값을 가지면서, 다시 이전 상태로 돌아가(BackTraking) 새로운 분기 상태 객체를 만들어야 한다. 그런데 객체 배열 복사를 위와 같이 해버리면, 다시 이전 상태로 돌아갈 수 없게 된다. 이미 원본 객체도 수정되어 버렸기 때문이다.

 

그래서 깊은 복사를 해야한다.

Fish[][] copy = new Fish[4][4];
for (...) {
    copy[i][j] = original[i][j] == null ? null : new Fish(...);
}

 

매 객체를 순회하면서 Fish 객체를 새로 생성해주는 깊은 복사를 해주어야만 한다.

---

그런데 변화할 Fish 객체가 적다면, 매번 모든 배열을 복사하는 것은 메모리에 부하가 크다.

거기다가 상태를 다르게 가져가야하는 분기점의 수가 많다면 상황은 더 악하된다.

 

이 때 사용하기 좋은 것이 in-place + BackTracking 전략이다.

어떤 전략일까? 바로..

 

별도의 상태 복사 없이 현재 상태를 그대로 사용하면서,

재귀 호출 전과 후에 직접 원상복구하는 방식

 

void dfs(state) {
    // 현재 상태 변경
    변경하기();

    // 다음 상태로 재귀
    dfs(nextState);

    // 상태 원상복구 (backtrack)
    복구하기();
}

 

DFS 란, 재귀를 하면서 해당 분기의 모든 처리가 끝난 다음에, 다시 이전의 메소드로 돌아간다(BackTracking).

 

다시 이전의 메소드(상태)로 돌아갔을 때, 상태가 일관적이어야 하므로,

다시 다른 분기를 타기전에 상태를 원상복구 해주는 것이다.

 

간단한 예시를 들자면 다음과 같다.

Fish eatenFish = tank[x][y];
int[] prevPos = fishPos[eatenFish.num].clone();

// 상태 변경
tank[x][y] = null;
fishPos[eatenFish.num][0] = -1;

// DFS 호출
dfs(...);

// 복구
tank[x][y] = eatenFish;
fishPos[eatenFish.num] = prevPos;

 

그러나 단점도 존재한다.

 

먼저 코드가 복잡해질 가능성이 존재하고, 디버깅이 어렵다는 점이다.

---

결론

자바에서 객체는 얕은 복사로 이루어진다.

따라서 DFS를 수행하며 객체를 복사할 때는 깊은 복사를 해야한다.

 

그러나 깊은 복사는 메모리 초과를 일으킬 수 있는 상황이 존재한다.

그럴 땐 in-place + BackTraking 전략을 사용하자.

 

그러나 이 전략은 이럴 때만 사용하자.

• 변경할 상태가 적고 단순할 때
• 배열이 크고, 깊은 복사에 대한 비용이 클 때
• 복구 로직이 간단할 때

그러나 이럴 때는 조심하자.

• 상태가 얽혀 있고 복잡할 때
• 배열이 그렇게 크지 않을 때
• 많은 상태가 변경되고, 복구 로직이 복잡할 때