[백준] 2210 : 숫자판 점프 - Java

• 백준 문제 URL

---

문제 요약

5×5 숫자판에서 임의의 칸에서 시작해서, 상/하/좌/우로 5번 이동(총 6자리 문자열 완성)하며 숫자를 이어 붙인다.
이렇게 만들어질 수 있는 서로 다른 6자리 수의 개수를 구하는 문제다.

---

핵심 아이디어

DFS + Set

이 문제는 “모든 시작점(25개)에서, 매 이동마다 4방향으로 뻗는” 완전탐색 형태라 DFS가 딱 맞는다.
그리고 같은 6자리 결과가 여러 경로에서 중복으로 나올 수 있으니, 결과를 Set에 넣어 중복 제거하면 최종적으로 set.size()가 정답이 된다.

여기서 중요한 포인트:

• 방문 체크(visited)는 필요 없음
  왜냐면 “한 칸을 다시 밟으면 안 된다” 제약이 없고, 오히려 같은 칸을 여러 번 지나가는 경로도 허용되기 때문이다.

---

탐색 설계(상태/종료조건)

상태(state)

DFS 함수가 들고 다니는 값은 3개다.

• current : 현재 좌표 {x, y}
• depth : 지금까지 이동한 횟수(또는 “추가로 붙인 횟수”)
• spot : 지금까지 이어 붙인 숫자 문자열

종료 조건

if (depth == 5) {
    caseSet.add(spot);
    return;
}

• 시작할 때 이미 한 자리(spot = grid[i][j])를 들고 들어감
• 그 뒤로 5번 더 이동하면서 숫자를 붙이면 총 6자리 완성
• 그래서 depth == 5일 때 spot을 set에 저장하고 종료

---

2차원 이동(dy/dx 패턴)

상/하/좌/우 이동을 dx, dy로 관리하면 코드가 깔끔해진다.

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

그리고 다음 좌표가 범위 안인지 체크한 뒤 재귀 호출:

int nx = current[0] + dx[k];
int ny = current[1] + dy[k];

if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5) {
    dfs(grid, new int[]{nx, ny}, depth + 1, spot + grid[nx][ny]);
}

(참고: 지금 코드에서 nx < grid[0].length && ny < grid[1].length로 되어 있는데, 5×5라서 동작은 하지만 의미상으론 nx < grid.length && ny < grid[0].length가 더 정확한 표현이다.)

---

왜 Set이면 방문 체크가 필요 없나?

• visited는 보통 “같은 칸을 다시 방문하면 안 되는 문제(미로, 섬 문제 등)”에서 필요하다.
• 숫자판 점프는 “중복 경로를 막는” 게 목적이 아니라 “가능한 모든 6자리 결과를 모으는” 게 목적이다.
• 따라서 중복 제거는 경로(좌표) 가 아니라 결과(문자열) 기준으로 해야 하고, 그 역할이 Set이다.

---

전체 코드(제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static Set<String> caseSet = new HashSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] grid = new int[5][5];

        for (int i = 0; i < 5; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                String spot = String.valueOf(grid[i][j]);
                dfs(grid, new int[]{i, j}, 0, spot);
            }
        }

        System.out.println(caseSet.size());
    }

    static void dfs(int[][] grid, int[] current, int depth, String spot) {
        if (depth == 5) {
            caseSet.add(spot);
            return;
        }

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int k = 0; k < 4; k++) {
            int nx = current[0] + dx[k];
            int ny = current[1] + dy[k];

            if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5) {
                dfs(grid, new int[]{nx, ny}, depth + 1, spot + grid[nx][ny]);
            }
        }
    }
}