[BOJ 12100] 2048 (Easy) – DFS, 로직 다 맞는데 틀렸던 이유 (Integer 비교)

2048(Easy) 문제는 최대 5번 이동했을 때 나올 수 있는 가장 큰 블록을 구하는 문제다.

접근 자체는 단순하다.

• 이동 횟수: 최대 5번
• 매번 이동 방향: 상 / 하 / 좌 / 우 (4가지)

⇒ 가능한 경우의 수: 4^5 = 1024
⇒ DFS로 전체 탐색하면 충분히 해결 가능

---

풀이 구조

1. DFS

 

static int N;
static int answer = 0;

static void DFS(int[][] board, int cnt){
    if (cnt == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                answer = Math.max(answer, board[i][j]);
            }
        }
        return;
    }

    for (int dir = 0; dir < 4; dir++) {
        int[][] newBoard = move(board, dir);
        DFS(newBoard, cnt + 1);
    }
}

• cnt가 5가 되면 현재 보드에서 최댓값을 구해서 answer 갱신
• 아니라면 4방향으로 move 하고 DFS 계속 진행

---

2. 이동 함수 (move)

각 방향마다 “한 줄씩” 처리하는 방식으로 구현했다.

아이디어:

1. 한 줄(row/column)에서 0이 아닌 값들만 뽑아서 리스트에 모으기
2. 리스트에서 인접한 같은 값끼리 한 번만 합치기
3. 다시 앞에서부터 채워넣기

static int[][] move(int[][] board, int c){
    int[][] arr = new int[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            arr[i][j] = board[i][j];

    // 위로 이동
    if (c == 0) {
        for (int x = 0; x < N; x++) {
            ArrayList<Integer> t = new ArrayList<>();
            for (int y = 0; y < N; y++) {
                if (arr[y][x] != 0) t.add(arr[y][x]);
                arr[y][x] = 0;
            }
            ArrayList<Integer> sum = new ArrayList<>();
            for (int i = 0; i < t.size(); i++) {
                if (i == t.size() - 1 || !t.get(i).equals(t.get(i + 1))) {
                    sum.add(t.get(i));
                } else {
                    sum.add(t.get(i) * 2);
                    i++;
                }
            }
            for (int i = 0; i < sum.size(); i++) {
                arr[i][x] = sum.get(i);
            }
        }
    }

    // 아래 / 왼쪽 / 오른쪽은 읽는 순서와 채우는 방향만 바꿔서 동일한 방식으로 처리

    return arr;
}

 

 

이동 로직 자체는 크게 문제 없었다.

---

근데 왜 계속 틀렸나? (핵심 버그)

내가 처음에 썼던 코드는 여기 한 줄이 문제였다.

 

if (i == t.size()-1 || t.get(i) != t.get(i+1)) {
    sum.add(t.get(i));
} else {
    sum.add(t.get(i) * 2);
    i++;
}

여기서 t는 ArrayList<Integer>다.

• t.get(i)의 타입은 Integer (래퍼 타입)
• !=는 값 비교가 아니라 “객체(참조)” 비교

자바에서 Integer는 -128 ~ 127까지는 캐싱되어서 == 비교가 우연히 맞는 경우가 많지만,
128 이상부터는 서로 다른 객체가 되어 == / !=로 비교하면 깨지기 시작한다.

그래서 예를 들어,

 

[128, 128]

이런 줄이 있을 때, 원래라면 256으로 합쳐져야 하는데,

• t.get(0)과 t.get(1)의 값은 둘 다 128이지만
• 서로 다른 Integer 객체라서 t.get(0) != t.get(1) 가 true가 됨
  → “다른 값이다”라고 판단하고 합치지 않음

결과적으로 큰 수(128, 256, 512, …)들이 전혀 합쳐지지 않아서,
DFS를 아무리 잘 돌려도 정답이 나오지 않는다.

---

수정: != 대신 .equals() 또는 int로 비교

방법 1: .equals() 사용

if (i == t.size() - 1 || !t.get(i).equals(t.get(i + 1))) {
    sum.add(t.get(i));
} else {
    sum.add(t.get(i) * 2);
    i++;
}

이렇게 고치고 제출하니 바로 맞았다.

---

정리

• 알고리즘(DFS + 4방향 완전탐색), move 로직 자체는 맞았는데
• Integer 비교에서 != 쓴 한 줄 때문에 계속 틀렸던 것
• 래퍼 타입 비교할 때는 ==, != 대신 .equals()를 쓰거나,
  아예 primitive로 꺼내서 비교하는 게 안전하다.

 

추가 정리 – Integer / Long / String 캐싱과 == 비교 이슈

1. 왜 Integer는 -128 ~ 127만 캐싱할까?

자바에서 Integer는 Integer.valueOf(int)를 통해 생성될 때
-128 ~ 127 범위의 값은 미리 만들어둔 객체를 재사용한다.

 

Integer a = 100;
Integer b = 100;

System.out.println(a == b);      // true (같은 객체)
System.out.println(a.equals(b)); // true (값 비교)

하지만 범위를 벗어나면 새 객체를 만든다.

 

Integer x = 128;
Integer y = 128;

System.out.println(x == y);      // false (다른 객체)
System.out.println(x.equals(y)); // true (값은 같다)

이걸 “Integer Cache”라고 부른다.

캐싱하는 이유

• 작은 정수(-128 ~ 127)는 매우 자주 쓰이는 값
• 매번 new Integer(...) 하면
  • 객체가 계속 만들어져서 메모리/GC 부하 증가
• 자주 쓰이는 범위만 미리 만들어서 재사용하면
  • 메모리 절약
  • 성능 향상

그래서 자주 사용 + 값 범위가 한정된 경우 캐싱이 유리하다.

---

2. Long도 비슷하게 캐싱한다

Long도 마찬가지로 Long.valueOf(long) 사용 시
기본 설정으로 -128 ~ 127 범위는 캐싱한다.

 

Long a = 100L;
Long b = 100L;
System.out.println(a == b);      // true (캐시 범위)
System.out.println(a.equals(b)); // true

Long x = 128L;
Long y = 128L;
System.out.println(x == y);      // false
System.out.println(x.equals(y)); // true

핵심 요약

• Integer, Long 같은 래퍼 타입은
  • 작은 값 일부만 캐싱
  • 나머지는 새 객체
• 따라서 == / != 비교는 값이 아닌 “객체 동일성” 비교라서
  동작이 일관되지 않는다

→ 값 비교는 무조건 .equals() 또는 primitive로 꺼내서 == 써야 한다.

---

3. String은 왜 캐싱(상수 풀, String Pool)을 쓸까?

String은 조금 다른 개념인 String Constant Pool을 사용한다.

 

String a = "hello";
String b = "hello";

System.out.println(a == b);      // true (동일한 상수 풀 객체)
System.out.println(a.equals(b)); // true

리터럴 "hello"는 Class 로딩 시 상수 풀에 하나만 올라가고,
동일한 리터럴을 쓰면 그 객체를 계속 재사용한다.

하지만 new String()을 쓰면 풀을 사용하지 않는다.

 

String a = "hello";
String b = new String("hello");

System.out.println(a == b);      // false (다른 객체)
System.out.println(a.equals(b)); // true

캐싱(풀) 쓰는 이유

• String은 불변(immutable)이라 공유해도 안전
• 동일한 문자열 리터럴이 코드에 많이 등장
• 풀을 사용하면
  • 중복 객체 생성 방지
  • 메모리 절약

---

4. 정리 – 언제 == 쓰고, 언제 .equals() 써야 하나?

• primitive 타입 (int, long, double, boolean …)
  → == / != 사용해도 됨 (값 비교)
• 래퍼 타입 (Integer, Long, Double, Boolean …)
  → 값 비교는 .equals() 사용
  → == / !=는 “같은 객체인지” 확인하는 용도 (대부분 쓰지 않는 게 맞음)
• String
  → 값 비교는 .equals()
  → ==는 “같은 String 객체인지(같은 참조인지)” 확인 용도

특히, 이번 2048 문제처럼:

• ArrayList<Integer>에 숫자들을 넣고
• 인접한 값이 같은지 비교해야 하는 상황에서는

// 절대 이렇게 쓰면 안 됨
t.get(i) == t.get(i + 1);    // X

// 이렇게 써야 함
t.get(i).equals(t.get(i + 1));  // O

// 또는
int a = t.get(i);
int b = t.get(i + 1);
if (a == b) { ... }             // O (primitive 비교)