[백준] 2210번. 숫자판 점프(JAVA)

문제

https://www.acmicpc.net/problem/2210

---

풀이(11분)

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

public class Main {
    static String grid[][] = new String[5][5]; // 숫자 격자판 (5x5 크기)
    static int dx[] = {0, 0, 1, -1}; // 상하좌우 이동을 위한 배열 (x 좌표 변화)
    static int dy[] = {1, -1, 0, 0}; // 상하좌우 이동을 위한 배열 (y 좌표 변화)
    static HashSet<String> uniqueNumbers = new HashSet<>(); // 중복을 방지하기 위한 HashSet

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

        // 5x5 숫자 격자 입력 받기
        for (int i = 0; i < 5; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                grid[i][j] = st.nextToken();
            }
        }

        // 모든 좌표에서 DFS 탐색 시작
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dfs(i, j, grid[i][j], 0);
            }
        }

        // 서로 다른 6자리 수의 개수 출력
        System.out.println(uniqueNumbers.size());
    }

    /**
     * 깊이 우선 탐색(DFS)으로 6자리 숫자 만들기
     * @param x 현재 x 좌표
     * @param y 현재 y 좌표
     * @param currentNumber 현재까지 만든 숫자 문자열
     * @param depth 현재까지 이동한 깊이 (0부터 시작, 5가 되면 종료)
     */
    public static void dfs(int x, int y, String currentNumber, int depth) {
        if (depth == 5) { // 6자리 숫자가 완성되었을 때
            uniqueNumbers.add(currentNumber); // HashSet에 추가
            return;
        }

        // 네 방향(상, 하, 좌, 우)으로 이동하면서 DFS 탐색
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            // 격자 범위를 벗어나지 않는 경우에만 이동
            if (0 <= nextX && nextX < 5 && 0 <= nextY && nextY < 5) {
                dfs(nextX, nextY, currentNumber + grid[nextX][nextY], depth + 1);
            }
        }
    }
}

 

간단한 dfs문제로 해결했다.

 

5x5라는 제한이 있기에 가능한 것으로, 약 25600번의 계산만 진행된다는 것을 이용했다.