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

1. 문제

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

2210번: 숫자판 점프

 

 

2. 풀이 과정

1. 시작점부터 중복 허용 즉, 방문 체크 없이 dfs로 탐색해서 5번 이동하는 경로를 찾는다.

2. 완성된 6자리 수는 boolean배열에 해당 수의 index에 해당하는 값을 true로 변경해주고 마지막에 true인 값을 가진 수의 개수를 출력한다.

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

public class Main {
    static int[][] map;
    static int result;
    static boolean visited[];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};

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

        map = new int[5][5];
        visited = new boolean[1_000_000];

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

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dfs(i, j, map[i][j], 0);
            }
        }

        System.out.println(result);
    }

    public static void dfs(int x, int y, int su, int cnt) {
        if (cnt == 5) {
            if(!visited[su]){
                visited[su] = true;
                result++;
            }
            return;
        }

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

            if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5) {
                dfs(nx, ny, su*10+map[nx][ny], cnt+1);
            }
        }
    }
}

 

 

결과