백준 2210 숫자판 점프 Java

정답률 70퍼센트가 넘는 백트래킹 문제인 숫자판 점프이다.

5*5 배열에 각각의 숫자가 상하좌우로 이동할 수 있을 때 나올 수 있는

6자리 수의 개수를 출력하면 되는 문제이다.

 

여태까지 풀어왔던 백트래킹 문제처럼 풀려했으나 계속해서 실패했다.

처음 수부터 출발해서 사용하는 경우와 사용하지 않는 경우의 수를

재귀 호출해서 백트래킹 하려고 했던 방식이다.

 

이 문제는 각각의 수가 전부 상하좌우로 이동할 수 있고 다녀갔던 곳도 재방문이 가능하므로

2중 for문으로 배열의 시작부터 끝까지 한 번씩 훑으면서 백트래킹을 해주면 되는 문제였다.

2중 for문으로 안 하고 1부터 24까지 for문을 한 번만 써서도 가능하다.

내가 짠 코드는 백트래킹이라고 하기도 좀 그런 게 되추적 하는 부분이 안 들어간다..

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Q2210 {
    static int [] dx = {1, -1, 0, 0};
    static int [] dy = {0, 0, 1, -1};
    
    public static void backtrack(int[][]a, List<String> ans, String str, int x, int y) {
        if(str.length()==6) {
            if(!ans.contains(str)) {
                ans.add(str);
            }
            return;
        }
        for(int k=0; k<4; k++) {
            if(x+dx[k] >=0 && x+dx[k]<5 && y+dy[k]>=0 && y+dy[k]<5) {
                backtrack(a, ans, str+a[x+dx[k]][y+dy[k]], x+dx[k], y+dy[k]);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int [][] a = new int[5][5];
        List<String> ans = new ArrayList<>();
        for(int i=0; i<5; i++) {
            for(int j=0; j<5; j++) {
                a[i][j] = scan.nextInt();
            }
        }
        for(int i=0; i<5; i++) {
            for(int j=0; j<5; j++) {
                backtrack(a, ans, a[i][j]+"", i, j);
            }
        }
        System.out.println(ans.size());
    }
}