[Java] 2210 숫자판 점프

문제

문제
5×5 크기의 숫자판이 있다.
각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다.
이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 
각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 

이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 
0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 
만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력
다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력
첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

문제 풀이

1. dfs 재귀 문제

2. 한 번 갔던 칸을 재방문 가능하기에 인접한 상하좌우 칸을 한 번 씩 다 둘러보며 값을 더해본다.

3. 문자열로 + 연산해서 더해가도 되지만 기존 값 * 10을 한 값에 더해주어도 되기 때문에 int를 사용

4. 값을 더해가다가 6자리가 되는 순간 해당 값 저장

5. 저장은 중복 값을 피하기 위해 HashMap을 사용

6. 칸 방문은 5 x 5 칸을 벗어나지만 않으면 되기 때문에 칸을 벗어나는 지만 탐색

자바 코드

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

public class BoardJump {
    private static final int[][] board = new int[5][5];
    private static final int len = 6;

    private static final int[] dr = {1, -1, 0, 0};
    private static final int[] dc = {0, 0, 1, -1};

    private static HashSet<Integer> result = new HashSet<>();

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

        for (int i = 0; i < 5; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < 5; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++) {
                search(1, board[i][j], i, j);
            }
        }

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

    private static void search(int idx, int num, int x, int y){
        if(idx == len){
            result.add(num);
            return;
        }

        for(int i = 0; i < 4; i++){
            int dx = x + dr[i];
            int dy = y + dc[i];

            if (boardCheck(dx, dy)) {
                search(idx + 1, (10 * num) + board[dx][dy], dx, dy);
            }
        }
    }

    private static boolean boardCheck(int x, int y){
        return x >= 0 && x < 5 && y >= 0 && y < 5;
    }
}