[2210] 숫자판 점프

🔗 문제 링크

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

🔍 문제 설명

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

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

⚠️ 제한사항

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

🗝 풀이 (언어 : Java)

모든 지점에서 시작하는 케이스를 조회한다. 중복 숫자는 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 {

    private static final int[] dx = new int[] {-1, 1, 0, 0};
    private static final int[] dy = new int[] {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] matrix = new int[5][5];
        for (int i = 0; i < 5; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 5; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        solution(matrix);
    }

    private static void solution(int[][] matrix) {
        Set<String> set = new HashSet<>(); //숫자 중복을 없애줄 Set
        //모든 지점에서 시작
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dfs(i, j, matrix, String.valueOf(matrix[i][j]), set);
            }
        }
        System.out.println(set.size());
    }

    private static void dfs(int x, int y, int[][] matrix, String str, Set<String> set) {
        //문자열 완성한 경우, Set에 넣고 종료
        if (str.length() == 6) {
            set.add(str);
            return;
        }
        //상하좌우 이동
        for (int i = 0; i < 4; i++) {
            //숫자판 범위를 벗어난 경우는 제외
            if (x + dx[i] < 0 || x + dx[i] >= 5
            || y + dy[i] < 0 || y + dy[i] >= 5) {
                continue;
            }
            //다음 방향으로 이동
            dfs(x + dx[i], y + dy[i], matrix, str + matrix[x + dx[i]][y + dy[i]], set);
        }
    }

}