숫자판 점프 - 2210

문제

풀이

import java.util.ArrayList;
import java.util.Scanner;

// 숫자판 점프 - S2 - DFS
public class ex2210 {

    static String[][] board = new String[5][5];
    static int[] dx ={0,1,0,-1};
    static int[] dy ={1,0,-1,0};
    static int cnt=0;
    static ArrayList<String> arr = new ArrayList<>();
    public static void DFS(int L,int x,int y,String tmp){
        if(L==5){
            if(!arr.contains(tmp)) arr.add(tmp);
        }
        else{
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0 && nx<5 && ny>=0 && ny<5){
                    DFS(L+1,nx,ny,tmp+board[nx][ny]);
                }

            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                board[i][j] = sc.next();
            }
        }

        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                DFS(0,i,j,board[i][j]);
            }
        }
        System.out.println(arr.size());
    }


}

임의의 위치에서 시작할 수 있으며, 4방향으로 이동가능하다. 5번 더 이동이 가능하고 6문자가 만들어지면 중복없이 몇가지 경우의 수가 나오는지 구하면 되는문제이다.

임의의 위치를 위해서 이중for문으로 DFS()를 호출한다. 그리고 tmp에 다음 좌표 문자들을 더해서 L(깊이)가 5가 되면 스탑! -> arr에 저장. 중복체크 필수