백준 2210 숫자판 점프 (자바)

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

2210번: 숫자판 점프

문제

1. 5 x 5 숫자판이 있다.
2. 각각의 칸에는 숫자(0~9) 적혀 있다.
3. 인접해 있는 네 방향으로 다섯 번 이동한다.
4. 각 칸에 적혀 있는 숫자를 차례로 붙이면 6자리 숫자가 된다.
   1. 이동할 때에는 한 번 거쳤던 칸을 거쳐도 된다.
   2. 0으로 시작하는 000123과 같은 수도 만들 수 있따.

풀이

1. 숫자판 크기 5x5로 정해져 있아 해당 map 배열을 만든다. 단, visit 배열은 만들지 않는다.
2. 6번 dfs 실행 후 6번이 되었을 때 set에 넣어준다. 
   1. set을 이용함으로써 중복을 제거한다.
3. set을 넣을 때 자료형은 String이다. 000123과 같은 수를 넣기 위해서이다.

코드

public class Main {
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static int[][] arr;
    static HashSet<String> list;
    static int N;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = 5;
        
        list = new HashSet<String>();
        arr = new int[N][N];
        String[] str;
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
                
            }
        }
        String s = new String();
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                //System.out.println("("+i+","+j+")");
                DFS(i,j,0,s);        
            }
        }
        System.out.println(list.size());
    }
 
    public static void DFS(int x, int y,int depth,String s) {
        //길이가 6일 때 set에 넣고 종료
        if(depth==6){
            list.add(s);
            return;
        }
        //상하좌우 이동할 수 있다. 왔던 길도 다시 올 수 있따.
        for(int i=0; i<4; i++){
            int nextX = dx[i]+x;
            int nextY = dy[i]+y;
            
            if(nextX<0 ||nextY<0||nextX>=N||nextY>=N){
                continue;
            }
            
            DFS(nextX,nextY,depth+1,s+arr[x][y]);
 
        }
        
    }
}