[BOJ] 백준 2210 - 숫자판 점프 (자바)

백트래킹......,,, DFS....,,,

DFS, 백트래킹 문제이다.

배열의 크기가 5x5이므로 전체 탐색을 해도 시간초과나 스택 오버플로우가 나지 않는다.

마음놓고 풀었다.

다만 String 형식으로 주고 받아야한다는 생각하는게  어려웠다.

풀이

1. 배열 0,0 부터 N-1, N-1까지 dfs 백트래킹을 실시한다.

2. 상하좌우로 계속해서 방문탐색한다. (왔던길도 다시 올 수 있다.)

3. 탐색의 깊이가 6일 경우 Set에 문자열을 넣는다. 이때 Set을 사용하는 큰 이유는 중복을 없애기 위함이다.

4. Set의 크기를 출력한다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.HashSet;
 
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]);
 
        }
        
    }
}